题目链接
题解
题目要求
∑i=1n∑j=1mσ0(gcd(i,j))[σ0(gcd(i,j))≤a] \sum_{i=1}^n\sum_{j=1}^m \sigma_0(\gcd(i,j))[\sigma_0(\gcd(i,j))\leq a] i=1∑nj=1∑mσ0(gcd(i,j))[σ0(gcd(i,j))≤a] 稍微转化一下就是∑T=1min⌊nT⌋⌊mT⌋∑k∣Tμ(Tk)σ0(k)[σ0(k)≤a] \sum_{T=1}^{\min} \lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T}\mu(\frac{T}{k})\sigma_0(k)[\sigma_0(k)\leq a] T=1∑min⌊Tn⌋⌊Tm⌋k∣T∑μ(kT)σ0(k)[σ0(k)≤a] 设f(T)=∑k∣Tμ(Tk)σ0(k)[σ0(k)≤a] f(T)=\sum_{k|T}\mu(\frac{T}{k})\sigma_0(k)[\sigma_0(k)\leq a] f(T)=k∣T∑μ(kT)σ0(k)[σ0(k)≤a] 考虑对于每一个σ0(k)=a\sigma_0(k)=aσ0(k)=a,更新其在对应位置上的fff,可以预处理出σ0\sigma_0σ0,然后以权值为关键字sort一边,离线处理询问,将询问以aaa为关键字sort一遍,用树状数组维护每个位置的fff。这里有一个小技巧,由于对2312^{31}231取模,因此可以利用自然溢出,用unsigned来记录答案,最后取模即可。
时间复杂度O(Tnlogn+nlog2n)O(T\sqrt{n}\log n+n\log^2 n)O(Tnlogn+nlog2n)。
代码
#include#include int read(){ int x=0,f=1; char ch=getchar(); while((ch<'0')||(ch>'9')) { if(ch=='-') { f=-f; } ch=getchar(); } while((ch>='0')&&(ch<='9')) { x=x*10+ch-'0'; ch=getchar(); } return x*f;} const int maxn=100000;const int maxq=20000;const unsigned mod=1<<31; namespace bit{ unsigned val[maxn+10]; int lowbit(int x) { return x&(-x); } int add(int pos,unsigned v) { while(pos<=maxn) { val[pos]+=v; pos+=lowbit(pos); } return 0; } unsigned getsum(int pos) { unsigned res=0; while(pos) { res+=val[pos]; pos-=lowbit(pos); } return res; }} struct data{ int id; unsigned val; bool operator <(const data &other) const { return val