LINK:LCM
T 组数据,\(T\leq 10000\)\(A,B\leq 4000000\)
简述一下这道题的式子: A,B 用 n,m 来代替 \(\sum_{i=1}{n}\sum_{j=1}^{m}\mu((i,j))^2LCM(i,j)\)
我们可以简单推式子 推出:
\(\sum_{w=1}^{n}w\cdot S(\frac{m}{w})\cdot S(\frac{n}{w})\cdot\sum_{x|w}x\cdot\mu(x)\mu(\frac{w}{x})^2\)
其中 S(x) 表示 \(\sum_{i=1}^xi\) 我们发现预处理后面的前缀和即可.
由于 A B 最大 4e6 这显然是在卡 nlnn 的算法 我们考虑线性筛出后面的东西.
设 f(w) 表示 \(\sum_{x|w}x\cdot\mu(x)\mu(\frac{w}{x})^2\) 那么 f(w) 其实是一个积性函数.
考虑 当 w 里存在 p 的时候 怎么筛 由于 f(p^3) 为 0 p 的更高次项也为 0 那么 f(p)=1-p,f(p^2) 直接由 f(p)*f(p) 类似的式子计算即可.
这算是一个小 trick 吧 当 w 存在 p 的时候 我们还是可以通过除以 p 来获取互质 从而利用积性函数的性质来求答案.
由于答案对 \(2^30\) 取模 但是我们可以开 unint 对 \(2^32\) 取模 最后 拿出后面的 30 位数即可.
- const int MAXN=4000010;
- int p[MAXN],mu[MAXN],v[MAXN];
- ui f[MAXN],sum[MAXN];
- int n,m,T,maxx,top;
- inline void prepare()
- {
- mu[1]=1;sum[1]=f[1]=1;
- rep(2,maxx,i)
- {
- if(!v[i])p[++top]=v[i]=i,mu[i]=-1,f[i]=(1-i);
- rep(1,top,j)
- {
- if(maxx/i<p[j])break;
- int ww=i*p[j];
- v[ww]=p[j];
- if(p[j]==v[i])
- {
- if(i/p[j]%p[j]!=0)f[ww]=-f[i/p[j]]*p[j];
- break;
- }
- mu[ww]=-mu[i];
- f[ww]=f[i]*f[p[j]];
- }
- sum[i]=sum[i-1]+f[i]*i;
- }
- }
- int main()
- {
- freopen("1.in","r",stdin);
- get(T);maxx=4000000;prepare();
- while(T--)
- {
- get(n);get(m);
- if(n>m)swap(n,m);
- int w1,w2,ww;
- ui ans=0;
- for(int i=1;i<=n;i=ww+1)
- {
- w1=n/i;w2=m/i;
- ww=min(n/w1,m/w2);
- ans+=(sum[ww]-sum[i-1])*((ui)(1+w1)*w1/2)*((ui)(1+w2)*w2/2);
- }
- printf("%u\n",ans&((1<<30)-1));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3477972.html