Description
定义 (f(n)) 为 (n) 所含质因子的最大幂指数
求
[sum _ {i=1}^{n} sum_{j=1}^{m} f(gcd(i,j))
]
[n,mle10^7
]
Solution
把 (gcd) 提出来，然后用一下两个套路可以轻松得到这个式子
[sum _ {T=1}^n lfloor frac n T
floorlfloor frac m T
floor sum _ {p|T} mu(p) f(frac T p)
]
然后瓶颈在于怎么处理后面的部分
令(g(x)=f * g= sumlimits _ {p|T} mu(p) f(frac T p))
所以瓶颈就在线性筛 (g(x))
我们注意到这个含有高次因子的 (mu(x)) 的值都是 (0)
同时(f(x)) 是满足互质 (max)
然后就不会了……（看题解看题解……）link
其实后面是分析部分：
对 (p) 分类讨论，如果 (p) 含有平方因子，对答案没有贡献，所以
[f(frac x p)=f(x) or f(x)-1
]
那么把求和转化成对于 (x) 的子集枚举
设最高次幂集({M}) 和 其他数集 ({O})
讨论发现如果 (f(frac x p)=f(x))
那么方案数是(2^{|O|} imes(2^{|M|-1}))
(|O|=0) 的时候会让留下来一个(f(x) or -f(x))
另一种情况的方案是(2^{|O|})种
看看 (mu) 的值还是个对半分，留下来的跟上面的那个正负性反着的
所以综上，(g_i) 只有三种取值……
就做完了
Code
#include<bits/stdc++.h>
using namespace std;
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
#define ll long long
const int N=1e7+10;
int pri[N],cnt,fl[N],g[N],f1[N];
inline void prework()
{
for(int i=2;i<N;++i)
{
if(!fl[i]) pri[++cnt]=i,g[i]=1,f1[i]=1;
for(int j=1;j<=cnt&&1ll*i*pri[j]<1ll*N;++j)
{
fl[pri[j]*i]=1;
if(i%pri[j]==0) break;
else if(f1[i]) g[i*pri[j]]=-g[i],f1[i*pri[j]]=1;
}
if(f1[i])
{
for(ll j=1ll*i*i;j<1ll*N;j*=i) g[j]=g[i];
}
}
for(int i=1;i<N;++i) g[i]+=g[i-1];
return ;
}
inline void work()
{
ll ans=0; int n=read(),m=read(); if(n>m) swap(n,m);
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=1ll*(g[r]-g[l-1])*(m/l)*(n/l);
} cout<<ans<<endl;
return ;
}
signed main()
{
prework();
int T=read();
while(T--) work();
return 0;
}
}
signed main(){return yspm::main()}