每日一题~abc356（对于一串连续数字 找规律，开数值桶算贡献）

添加链接描述

题意：对于给定的n,m 。计算0~n 每一个数和m & 之后，得到的数 的二进制中 1的个数的和。

一位一位的算。最多是60位。

我们只需要计算 在 1-n这些数上，有多少个数 第i位 为1.
因为是连续的自然数，每一位上1 的出现 必然存在某种规律。
我们从 第零位 开始计数。
第 i 位 的 1 的出现周期是 2^(i+1) ，其中前一半是0，后一半是1.（数量是 2^i个）
想明白这一点之后，
对于整除的那一部分，第i位的贡献是

int w=(long long )1<<i;
n/(w*2)*w 

那么整的部分算完了，接下来算 散 的那一部分

这里可以自己找个例子，算一下。不然很容易错。
max((long long )0,n%(2*w)-w+1)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=998244353;
signed main()
{
	int n,m;cin>>n>>m;
	int ans=0;
	for (int i=0;i<60;i++)
	{
		if (m>>i &1){
			int w=(long long )1<<i;
			ans+=n/(w*2)*w+max((long long )0,n%(2*w)-w+1);
			ans%=mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

可以注意到
ai的数值非常小，不到1e6，这个时候 就有很大可能 开数值桶。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int wc=1e6+5;
int a[wc],s[wc];
 
signed main()
{
	int n;cin>>n;
	int t=0;
	for (int i=0;i<n;i++)
	{
		cin>>t;a[t]++;
	}
	for (int i=1;i<=wc;i++){
		s[i]=s[i-1]+a[i];
	}
	
	int ans=0;
	for (int i=1;i<=wc;i++)
	{
		ans+=a[i]*(a[i]-1)/2;//选择两个相同的数的贡献
		//枚举左端点 ，比枚举右端点好，因为右端点不一定正好到wc，
		//后面可能还有一些比a[i]大的数 
		for (int j=i;j<=wc;j+=i)
		{
			ans+=a[i]*(j/i)*(s[min(wc,j+i-1)]-s[j==i?i:j-1]);
			非常优美的代码^_^
		 } 
	}
	cout<<ans<<"\n";
	return 0;
}

时间复杂度： 第二层for里面，因为每次都是 i 的倍数，并且有一个上界 wc，所以是调和级数的复杂度，
复杂度为 log wc。
总的复杂度为 wc* log wc