Label

欧拉函数

Description

给定多个正整数 n ( 1 < n < 2 31 ) n(1<n<2^{31}) n(1<n<231)，请求出：
∑ i = 1 n g c d ( i , n ) \sum_{i=1}^{n}gcd(i,n) i=1∑n​gcd(i,n)

Solution

由于直接枚举 i i i暴力求肯定会TLE，故我们不考虑 i i i的取值对答案的贡献，而是考虑每一种 g c d ( i , n ) gcd(i,n) gcd(i,n)的取值对答案的贡献。

设 g c d ( i , n ) = d gcd(i,n)=d gcd(i,n)=d，那么每一个满足该条件的数 i i i一定满足如下性质：

g c d ( i , n ) = d ↔ g c d ( i d , n d ) = 1 gcd(i,n)=d\leftrightarrow gcd(\frac{i}{d},\frac{n}{d})=1 gcd(i,n)=d↔gcd(di​,dn​)=1

这样一来，又出现了互质的条件，那么，满足上述条件的 i i i的个数便为 ∑ i = 1 n [ g c d ( i d , n d ) = = 1 ] = φ ( ⌊ n d ⌋ ) \sum_{i=1}^{n}[gcd(\frac{i}{d},\frac{n}{d})==1]=\varphi(\lfloor \frac{n}{d}\rfloor) ∑i=1n​[gcd(di​,dn​)==1]=φ(⌊dn​⌋)。

所以， d d d对答案的贡献为 d φ ( ⌊ n d ⌋ ) d\varphi(\lfloor \frac{n}{d}\rfloor) dφ(⌊dn​⌋)。

由于 g c d ( i , n ) = d gcd(i,n)=d gcd(i,n)=d，故所有 d d d的取值构成的集合等于 n n n的约数集合，所以：
∑ i = 1 n g c d ( i , n ) = ∑ d ∣ n d φ ( ⌊ n d ⌋ ) \sum_{i=1}^{n}gcd(i,n)=\sum_{d|n}d\varphi(\lfloor \frac{n}{d}\rfloor) i=1∑n​gcd(i,n)=d∣n∑​dφ(⌊dn​⌋)

最后注意两点：

1、如何枚举 d d d： O ( n ) O(\sqrt n) O(n ​)做法枚举 n n n的正约数即可。

2、 n n n太大：预处理出一部分 φ ( n ) \varphi(n) φ(n)，剩下的部分 O ( n ) O(\sqrt n) O(n ​)单独求。

总体复杂度：看起来是 O ( n ) O(n) O(n)的，但由于我们预处理出相当数量的 φ ( n ) \varphi(n) φ(n)且整数的约数个数远远达不到 2 n 2\sqrt n 2n ​的理论上界，所以复杂度可行。

Summary

两条重要性质：

1、 g c d ( i , n ) = d ↔ g c d ( i d , n d ) = 1 gcd(i,n)=d\leftrightarrow gcd(\frac{i}{d},\frac{n}{d})=1 gcd(i,n)=d↔gcd(di​,dn​)=1

2、 ∑ i = 1 n g c d ( i , n ) = ∑ d ∣ n d φ ( ⌊ n d ⌋ ) \sum_{i=1}^{n}gcd(i,n)=\sum_{d|n}d\varphi(\lfloor \frac{n}{d}\rfloor) ∑i=1n​gcd(i,n)=∑d∣n​dφ(⌊dn​⌋)

Code

#include<cstdio>
#include<iostream>
#define ri register int
#define ll long long
using namespace std;

const int MAXN=5e6;
int cnt;
ll N,prime[MAXN>>2],phi[MAXN+20],phia,phib,ans;
bool isprime[MAXN+20];

ll Phi(ll x)//求phi(x)一般用利用容斥原理推出的公式，复杂度O(sqrt(n)) 
{
	register ll phix=x;
	for(ll i=2;i*i<=x;++i)
		if(x%i==0)
		{
			phix=phix/i*(i-1);
			while(x%i==0)	x/=i;
			
		}
	if(x>1)	phix=phix/x*(x-1);
	return phix;
}

void Phi()//O(n)求1~N的欧拉函数 
{
	isprime[1]=true; phi[1]=1LL;
	for(ri i=2;i<=MAXN;++i)
	{
		if(!isprime[i])
		{
			prime[++cnt]=(ll)i;
			phi[i]=(ll)i-1;	
		}
		for(ri j=1;j<=cnt&&i*(int)prime[j]<=MAXN;++j)
		{
			isprime[i*(int)prime[j]]=true;
			if(i%prime[j]==0)	phi[i*(int)prime[j]]=phi[i]*prime[j];
			else	phi[i*(int)prime[j]]=phi[i]*phi[prime[j]];
			if(i%prime[j]==0)	break;
		}
	}
}

int main()
{
	Phi();
	while(~scanf("%lld",&N))
	{
		ans=0;
		for(ll i=1;i*i<=N;++i)
		{
			if(N%i==0)
			{
				if(i<=MAXN)	phia=phi[(int)i];
				else	phia=Phi(i);
				if(N/i<=MAXN)	phib=phi[(int)(N/i)];
				else	phib=Phi(N/i);
				if(i!=N/i)	ans+=N/i*phia+i*phib;
				else	ans+=i*phia;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}