令\(p=\lfloor\frac{n-r}m\rfloor\)，则我们其实是要对所有\(0\le i \le 29\)求\(\sum_{j=0}^p (\lfloor \frac{mj+r}{2^i}\rfloor mod \ 2)\)。右边那个东西如果没有那个\(mod\ 2\)，其实就是类欧几里得算法的最基本情况。
顺便说一句，oiwiki的搜索功能问题很大，比如在搜索框直接搜类欧根本搜不到。
进一步观察发现，如果我们能对每个\(0\le i\le 29\)求出\(\sum_{j=0}^p \lfloor \frac{mj+r}{2^i}\rfloor\)，其实也已经能计算答案了。令在\(i\)时求出的右边式子的值为\(f_i\)。则对于任意i，在\(f_i\)中，每个第i位的1都被计算了1次，每个第i+1位的1都被计算了2次，……，每个第j位的1都被计算了\(2^{j-i}\)次。令\(g_i\)表示实际上第i位的1的总个数，则\(g_i=f_i-\sum_{j>i}2^{j-i}g_j\)。
总复杂度\(O(tlog^2n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define pdd pair <double,double>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
LL f(LL a,LL b,LL c,LL n)
{
LL add=n*(n+1)/2*(a/c)+(n+1)*(b/c);
a%=c;b%=c;
if(a==0) return add+b/c*(n+1);
LL m=(a*n+b)/c;
LL ret=n*m-f(c,c-b-1,a,m-1);
ret+=add;
return ret;
}
LL t,n,m,r,val[40];
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n>>m>>r;
rep(i,35) val[i]=0;
LL mxi=(n-r)/m;
rep(i,30) val[i]=f(m,r,1LL<<i,mxi);
LL ans=0;
for(int i=29;i>=0;--i)
{
for(int j=i+1;j<=29;++j) val[i]-=val[j]*(1LL<<(j-i));
ans+=val[i];
}
printf("%lld\n",ans);
}
termin();
}