题目
多组询问求
[sum_{i=1}^nsum_{j=1}^m{|mu(gcd(i,j))|*lcm(i,j)}pmod {2^{30}}
]
(Tleq 10^4,n,mleq 4*10^6)
分析
设 (f(n,m)=C(n+1,2)*C(m+1,2)) ，
则根据Crash的数字表格类似的方法可以得到
[large sum_{d=1}^{min{n,m}}dmu^2(d)sum_{t=1}^{min{lfloorfrac{n}{d}
floor,lfloorfrac{m}{d}
floor}}mu(t)t^2*f(lfloorfrac{n}{td}
floor,lfloorfrac{m}{td}
floor)
]
这样整除分块只能做到 (O(min{n,m}))，多组数据就不行了，
考虑维护 (i=t*d)，则
[large =sum_{i=1}^{min{n,m}}f(lfloorfrac{n}{i}
floor,lfloorfrac{m}{i}
floor)*(isum_{d|i}mu(d)dmu^2(frac{i}{d}))
]
考虑 (g(n)=sum_{d|i}mu(d)dmu^2(frac{i}{d})) 是一个积性函数，
线性筛时只要质因子次数大于2时(g(n)=0)，
否则若质因数次数等于2则(g(n*p)=-g(n)*p)
那就可以做到(O(Tsqrt{min{n,m}}))了
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=10000000;
const int mod=100000009;
typedef long long lll;
int f[N|15],prime[N|15],v[N|15],Cnt;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed min(int a,int b){return a<b?a:b;}
inline lll answ(lll n,lll m){return (n*(n+1)>>1)%mod*((m*(m+1)>>1)%mod)%mod;}
inline signed mo(int x,int y){return x+y>=mod?x+y-mod:x+y;}
signed main(){
f[1]=1;
for (rr int i=2;i<=N;++i){
if (!v[i]) prime[++Cnt]=i,f[i]=mod-i+1;
for (rr int j=1;j<=Cnt&&prime[j]<=N/i;++j){
v[i*prime[j]]=1;
if (i%prime[j]==0){
f[i*prime[j]]=f[i];
break;
}
f[i*prime[j]]=1ll*f[i]*f[prime[j]]%mod;
}
}
for (rr int i=2;i<N;++i) f[i]=mo(f[i-1],1ll*f[i]*i%mod);
for (rr int T=iut();T;--T){
rr int n=iut(),m=iut(),ans=0;
if (n>m) n^=m,m^=n,n^=m;
for (rr int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans=mo(ans,answ(n/l,m/l)*(f[r]-f[l-1]+mod)%mod);
}
print(ans),putchar(10);
}
return 0;
}