(资料图)
题目链接
令\(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 #define rep(i,n) for(int i=0;i#define pdd pair #define fi first#define se second#define mpr make_pair#define pb push_backvoid 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<=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();} 
