Find the sum of popcounts of all integers between $1$ and $N$, inclusive, such that the remainder when divided by $M$ equals $R$.Problem Statement
Here, the popcount of a positive integer $X$ is the number of $1$s in the binary notation of $X$, that is, the number of non-negative integers $k$ such that the $2^k$s place is $1$.
For each input, process $T$ test cases.Constraints
Input
The input is given from Standard Input in the following format. The first line is as follows:
$T$
$T$ test cases follow. Each of them is given in the following format:
$N$ $M$ $R$
Output
Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case.
Sample Input 1
2 12 5 1 6 1 0
Sample Output 1
6 9
In the $1$-st test case, the popcount of $1$ is $1$, the popcount of $6$ is $2$, and the popcount of $11$ is $3$, so $1+2+3=6$ should be printed.
In the $2$-nd test case, the popcount of $1$ is $1$, $2$ is $1$, $3$ is $2$, $4$ is $1$, $5$ is $2$, and $6$ is $2$, so $1+1+2+1+2+2=9$ should be printed.
看到这种形式，就能想到类欧。
考虑每一位分别计算，那么第 \(x\) 位大概是一个 \(\sum\limits_{i=0}^{\lfloor\frac {n-r}m\rfloor}\lfloor\frac {im+r}{2^x}\rfloor\) 之类的东西。但这样弄只会弄出来所有模 \(m\) 余 \(r\) 的数二进制下前 \(x\) 位所表示的二进制数之和，而不能得到刚好第 \(x\) 位为1的数的数量。
但是可以容斥一下。设 \(f_x\) 为用类欧求出的前 \(x\) 位之和，那么 \(f_x-2f_{x+1}\) 就是刚好第 \(x\) 位为1的数的数量了。
#include<cstdio>
typedef long long LL;
int t,n,m,r;
LL f[35],ans;
LL calc(int a,int b,int c,int n)
{
if(!a)
return (b/c)*(n+1);
if(a>=c||b>=c)
return 1LL*n*(n+1)/2*(a/c)+1LL*(n+1)*(b/c)+calc(a%c,b%c,c,n);
LL m=(1LL*a*n+b)/c;
return n*m-calc(c,c-b-1,a,m-1);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&r);
for(int i=0;i<=30;i++)
f[i]=calc(m,r,1<<i,(n-r)/m);
for(int i=ans=0;i<=30;i++)
f[i]-=f[i+1]*2,ans+=f[i];
// putchar('\n');
printf("%lld\n",ans);
}
}