P5176 公约数

P5176 公约数

说在前面的话：

这题后面的线性筛和 P4449 于神之怒加强版 很像，建议这两道题连着做，巩固一下非常规函数线性筛顺便水个双倍经验。但是网上于神之怒的题解都过于简略（我比较菜），看不懂，做于神之怒的时候很痛苦，因此本文线性筛的过程尽量详细写,让初学者看懂，看不懂欢迎在评论区提问，NOIP前应该能做到1天内回复。

[sum_{i=1}^nsum_{j=1}^msum_{k=1}^pgcd(icdot j,icdot k,jcdot k) imes gcd(i,j,k) imes left(frac{gcd(i,j)}{gcd(i,k) imes gcd(j,k)}+frac{gcd(i,k)}{gcd(i,j) imes gcd(j,k)}+frac{gcd(j,k)}{gcd(i,j) imes gcd(i,k)} ight) ]

那个 (gcd(ij,jk,ki)) 一看就是要化掉的。

显然应该从质因子的幂次入手，设 (i=p^a,j=p^b,k=p^c)

那么 (p) 对 (gcd(ij,jk,,ki)) 的贡献就是 (p^{min(a+b,b+c,c+a)})

考虑构造一个东西来表示 (min(a+b,b+c,c+a)) 。不妨 (ale ble c) （显然排序不会影响结果）

(min(a+b,b+c,c+a)=a+b=min(a,b)+min(b,c)+min(a,c)-min(a,b,c))

转成 (gcd) 的写法就是 (gcd(ij,jk,ki)=dfrac{gcd(i,j)gcd(j,k)gcd(k,i)}{gcd(i,j,k)})

带回原式发现良心出题人非常非常非常良心地帮你约掉了 (gcd(i,j,k)) 这种三元 (gcd) 以及所有分母

化简一下，原式(=sumlimits_{i=1}^{A}sumlimits_{j=1}^{B}sumlimits_{k=1}^{C}gcd(i,j)^2+gcd(j,k)^2+gcd(k,i)^2)

发现凉心出题人非常非常非常凉心把 (gcd) 平方了。

原式显然可以分成三部分算。

先算

[sum_{i=1}^{A}sum_{j=1}^{B}sum_{i=1}^{C}gcd(i,j)^2\ =Csum_{i=1}^{A}sum_{j=1}^{B}gcd(i,j)^2\ =Csum_{d=1}^{A} sum_{i=1}^{A}sum_{j=1}^{B}[gcd(i,j)==d]d^2\ =Csum_{d=1}^{A}d^2sum_{i=1}^{frac{A}{d}}sum_{j=1}^{frac{B}{d}}[gcd(i,j)==1]\ =Csum_{d=1}^{A}d^2sum_{i=1}^{frac{A}{d}}sum_{j=1}^{frac{B}{d}}sum_{x|gcd(i,j)}mu(x)\ =Csum_{d=1}^{A}d^2sum_{x=1}^{frac{A}{d}}mu(x)dfrac{A}{dx}dfrac{B}{dx}\ =Csum_{d=1}^{A}d^2sum_{T=1,d|T}^{A}mu(dfrac{T}{d})dfrac{A}{T}dfrac{B}{T}\ =sum_{T=1}^{A}dfrac{A}{T}dfrac{B}{T}sum_{d|T}d^2mu(dfrac{T}{d}) ]

现在的问题在于 (f(T)=sum_{d|T}d^2mu(dfrac{T}{d})) ，这个东西一出来就可以 (O(sqrt{n})) 整除分块了。

仔细观察发现这是个积性函数，可以线性筛， (2e7) 怕他啥（(color{black}{ exttt{c}}color{red}{ exttt{yn2006}}) (O(nln n)) 暴力筛都过去了）。

令 (pin prime) ，则

[f(p)=mu(1) imes p^2+mu(p) imes 1^2=p^2-1\ ]

接下去处理掉 (p|i) 的情况就可以线性筛了。

设 (x) 为 (p) 在 (T) 中的最高幂次

发掘 (mu) 的性质，当且仅当 (d=p^x) 或 (d=p^{x-1}) 时有贡献（(mu(dfrac{T}{d})!=0)）。

带入得

(f(p^x)=p^{2x}-p^{2(x-1)})

(f(p^{x+1})=p^{2(x+1)}-p^{2x}=p^2(p^{2x}-p^{2(x-1)})=p^2f(p^x))

( herefore f(ip)=f(i) imes p^2(p|i)) ，综合如下：

[f(T)= egin{cases} T^2-1(Tin mathcal{prime})\ f(i)*p^2(p|i)\ f(i)*f(p)(otherwise) end{cases} ]

可以线性筛了

提供一组大样例以供调试

Input
1
10000000 5000000 20000000
Output
913785109

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define pb(x) push_back(x)
#define mkp(x,y) make_pair(x,y)
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int N=20000005;
const int mod=1000000007;
int A,B,C;
int pri[N/10],cnt,s[N];
bool vis[N];
void Sieve(const int N=20000000){
	s[1]=1;
	for(int i=2;i<=N;++i){
		if(!vis[i])pri[++cnt]=i,s[i]=1ll*i*i%mod-1;
		for(int j=1;j<=cnt&&i*pri[j]<=N;++j){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){s[i*pri[j]]=1ll*s[i]*pri[j]%mod*pri[j]%mod;break;}
			s[i*pri[j]]=1ll*s[i]*s[pri[j]]%mod;
		}
	}
	for(int i=1;i<=N;++i)s[i]=(s[i]+s[i-1])%mod;
}
int f(int A,int B,int C){
	int res=0;
	for(int l=1,r,mx=min(A,B);l<=mx;l=r+1){
		r=min(A/(A/l),B/(B/l));
		res=(res+1ll*(A/l)*(B/l)%mod*(s[r]-s[l-1])%mod)%mod;
	}
	return 1ll*res*C%mod;
}
signed main(){
	Sieve();
	for(int T=read();T;--T){
		A=read(),B=read(),C=read();
		printf("%d
",(((f(A,B,C)+f(B,C,A))%mod+f(C,A,B))%mod+mod)%mod);
	}
}