性質1：質數n的歐拉函數為n-1.

性質2：如果p，q都是質數，那么? ( p ? q ) = ? ( p ) ? ? ( q ) = ( p ? 1 ) ? ( q ? 1 )

????????證明：p，2p....q*p都不與q*p互質，q同理，所以總的不互質個數應該是p+q-1，所以? ( p ? q )=p*q-（p+q-1）=（p-1）*（q-1）。

性質3：如果p是質數，那么

? ? ? ? 證明：同性質2，p，p*2....，因為p要乘以才到，所以一共有個數。

性質4：對任意正整數n=,就是將其素數冪分解，

????????證明：由性質2和性質3進行拆分，對于單個提取變成

最后變成,前面那些項的積等于n

性質5：若a為質數,b mod a=0（b是a的倍數）,? ( a ? b ) = ? ( b ) ? a?

const int Maxn=1e7;
int phi[Maxn];//記錄數的約數個數(歐拉函數) 
bool vis[Maxn];//記錄數字是否訪問 
int prime[Maxn];//保存素數 vis[1]=1;//1不是素數 for(int i=2;i<=n;i++){if(!vis[i])//沒有被訪問，也就是沒有被篩掉,說明是素數 {vis[i]=!vis[i];prime[++prime[0]]=i;phi[i]=i-1;}for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){vis[i*prime[j]]=true;if(i%prime[j]==0)//a%b==0，那么phi[a*b]=b*phi[a] {phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);//兩者互素 }}

題目鏈接

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const ll mod=998244353;
const int Maxn=2e5+10;int phi[Maxn];//記錄數的約數個數(歐拉函數) 
bool vis[Maxn];//記錄數字是否訪問 
int prime[Maxn];//保存素數
void init(){vis[1]=1;//1不是素數 phi[1]=1;for(int i=2;i<=Maxn;i++){if(!vis[i])//沒有被訪問，也就是沒有被篩掉,說明是素數 {vis[i]=!vis[i];prime[++prime[0]]=i;phi[i]=i-1;}for(int j=1;j<=prime[0]&&i*prime[j]<=Maxn;j++){vis[i*prime[j]]=true;if(i%prime[j]==0)//a%b==0，那么phi[a*b]=b*phi[a] {phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);//兩者互素 }}
} 
void solve(){init();int n;cin>>n;ll ans=0;for(int i=1;i<n;i++){ans+=phi[i]*2;}cout<<ans+1;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while (t--){solve();}return 0;
}