添加鏈接描述
題意：對于給定的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
