原题 P2303 [SDOI2012] Longge 的问题

推式子：

$$\begin{align} &\displaystyle\sum\limits_{i=1}^n \gcd(i,n)\notag\\ =&\sum\limits_{d|n}d\sum\limits_{i=1}^n[\gcd(i,n)=d]\notag\\ =&\sum\limits_{d|n}d\sum\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1] \notag\\ =&\sum\limits_{d|n}d\varphi(\frac{n}{d})\notag \end{align} $$

这里给出一种$O(logn)$算$\varphi(\frac{n}{d})$的方法

发现$\frac{n}{d}$一定是$n$的因数，所以它的质因子一定是$n$的质因子。

所以我们可以先处理出$n$的所有质因子，然后算的时候只考虑这些质因子就行。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n;
const int N=1e5*1.01;
bitset<N>pvis;
int pri[N],ptot;
int np[N],ntt;
int phi(int x){
	int ret=x;
	for(int i=1;i<=ntt;i++){
		if(x%np[i]==0){
			ret=ret/np[i]*(np[i]-1);
		}
	}return ret;
}
signed main() {
	for(int i=2;i<=N;i++){
		if(pvis[i]==0){
			pri[++ptot]=i;
		}for(int j=1;pri[j]*i<=N&&j<=ptot;j++){
			pvis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int nn=n; 
	for(int i=1;pri[i]<=sqrt(n);i++){
		if(n%pri[i]==0){
			np[++ntt]=pri[i];
			while(n%pri[i]==0) n/=pri[i];
		}
	}if(n!=1) np[++ntt]=n;
	n=nn; 
	int ans=0;
	for(int i=1;i<=sqrt(n);i++){
		if(n%i==0){
			ans=ans+i*phi(n/i);
			if(i*i!=n){
				ans=ans+(n/i)*phi(i);
			}
		}
	}cout<<1ull*ans;
	return 0;
}