P2158 [SDOI2008] 仪仗队 - Description
给定正整数 \(n\)，求
\[\sum_{i=1}^{n-1} \sum_{j=1}^{n-1} \left [ \gcd(i,j)=1 \right ]
\]
\(1\le n\le 5\times 10^4\)。
P2158 [SDOI2008] 仪仗队 - Solution
\[\begin{aligned}
\sum_{i=1}^{n-1} \sum_{j=1}^{n-1} \left [ \gcd(i,j)=1 \right ] &= 2\times \sum_{i=1}^{n-1} \sum_{j=1}^i \left [ \gcd(i,j) =1\right ]-1\\
&=2\times \sum_{i=1}^{n-1} \varphi(i) -1
\end{aligned}
\]
最后答案要加上第一行和第一列的 \(2\)，记得特判 n=1。
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,ans;
long long tot,Prime[100005],vis[100005],phi[100005];
inline void init(){phi[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){Prime[++tot]=i;phi[i]=i-1;}for(int j=1;j<=tot&&i*Prime[j]<=n;j++){vis[i*Prime[j]]=1;if(i%Prime[j]==0){phi[i*Prime[j]]=phi[i]*Prime[j];break;}else{phi[i*Prime[j]]=phi[i]*phi[Prime[j]];}}}return;
}
signed main(){cin>>n;if(n==1){cout<<0<<endl;return 0;}init();for(int i=1;i<n;i++){ans+=phi[i];}cout<<ans*2+1<<endl;return 0;
}
P2568 GCD - Description
给定正整数 \(n\)，求
\[\sum_{i=1}^n \sum_{j=1}^n \left [ \gcd(i,j)\in \textup{\textbf{Prime}} \right ]
\]
\(1\le n\le 10^7\)。
P2568 GCD - Solution
\[\begin{aligned}
\sum_{i=1}^n \sum_{j=1}^n \left [ \gcd(i,j)\in \textup{\textbf{Prime}} \right ]&= \sum_{p\in \textup{\textbf{P}}}\sum_{i=1}^n\sum_{j=1}^n \left [ \gcd(i,j)=p \right ]\\&=\sum_{p\in \textup{\textbf{P}}}\sum_{i=1}^{\lfloor\frac{n}{p} \rfloor}\sum_{j=1}^{\lfloor\frac{n}{p} \rfloor} \left [ \gcd(i,j)=1 \right ]\\&=\sum_{p\in \textup{\textbf{P}}}\sum_{i=1}^{\lfloor\frac{n}{p} \rfloor}\left [ 2\times \left ( \sum_{j=1}^{i} \left [ \gcd(i,j)=1 \right ]\right ) -1\right ]\\&=\sum_{p\in \textup{\textbf{P}}}\sum_{i=1}^{\lfloor\frac{n}{p} \rfloor} \left ( 2\times \varphi(i)-1\right )
\end{aligned}
\]
此处应有前缀和/整除分块，但是我懒，不写了，反正能过
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,Prime[10000005],tot,vis[10000005],phi[10000005],ans;
inline void init(){phi[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){Prime[++tot]=i;phi[i]=i-1;}for(int j=1;j<=tot&&i*Prime[j]<=n;j++){vis[i*Prime[j]]=1;if(i%Prime[j]==0){phi[i*Prime[j]]=phi[i]*Prime[j];break;}else{phi[i*Prime[j]]=phi[i]*phi[Prime[j]];}}}return;
}
signed main(){cin>>n;init();
// for(int i=1;i<=n;i++){
// cout<<phi[i]<<" ";
// }
// cout<<endl;for(int i=1;Prime[i]<=n&&i<=tot;i++){int cnt=0;for(int j=1;j<=n/Prime[i];j++){cnt+=2*phi[j];}ans+=(cnt-1);}cout<<ans<<endl;return 0;
}
P2398 GCD SUM - Description
给定正整数 \(n\)，求
\[\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)
\]
\(1\le n\le 10^5\)。
P2398 GCD SUM - Solution
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)&=\sum_{d=1}^n \left (d\times \sum_{i=1}^n \sum_{j=1}^n \left [ \gcd(i,j)=d\right ]\right )\\
&=\sum_{d=1}^n \left ( d\times \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}\left [ \gcd(i,j)=1\right ] \right )\\&=\sum_{d=1}^n \left ( d\times \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} 2 \left (\sum_{j=1}^i \left [ \gcd(i,j)=1 \right ] \right ) -1 \right )\\&=\sum_{d=1}^n \left ( d\times \left ( \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} 2\times \varphi(i) -1 \right ) \right )\end{aligned}
\]
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,ans;
long long tot,Prime[100005],vis[100005],phi[100005];
inline void init(){phi[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){Prime[++tot]=i;phi[i]=i-1;}for(int j=1;j<=tot&&i*Prime[j]<=n;j++){vis[i*Prime[j]]=1;if(i%Prime[j]==0){phi[i*Prime[j]]=phi[i]*Prime[j];break;}else{phi[i*Prime[j]]=phi[i]*phi[Prime[j]];}}}return;
}
signed main(){cin>>n;init();for(int i=1;i<=n;i++){
// cout<<phi[i]<<" ";int tmp=0;for(int j=1;j<=n/i;j++){tmp+=2*phi[j];}tmp--;ans+=tmp*i;}cout<<ans<<endl;return 0;
}
HDU2588 GCD - Description
多测，每组数据给定两个正整数 \(n\) 和 \(m\)，求
\[\sum_{i=1}^n \left [ \gcd(i,n)\ge m \right ]
\]
\(1\le T\le 100,2\le n\le 10^9,1\le m\le n\)。
HDU2588 GCD - Solution
\[\begin{aligned}
\sum_{i=1}^n \left [ \gcd(n,i)\ge m\right ] &=\sum_{d=m}^n \sum_{i=1}^n \left [ \gcd(n,i)=d \right ]
\end{aligned}
\]
当 \(d\) 给定时，满足条件的 \(i\) 可以写成 \(i=i'd\)，同理有 \(n=n'd\)，其中 \(\gcd(i',n')=1\)。而所求即为 \(i'd\) 的个数，为 \(\varphi(n')\)。
\[\begin{aligned}\sum_{d=m}^n \sum_{i=1}^n \left [ \gcd(n,i)=d \right ]&=\sum_{d\mid n} \varphi(\frac{n}{d})
\end{aligned}
\]
P2303 [SDOI2012] Longge 的问题 - Description
给定正整数 \(n\)，求
\[\sum_{i=1}^n \gcd(n,i)
\]
\(1\le n\le 2^{32}\)。
P2303 [SDOI2012] Longge 的问题 - Solution
\[\begin{aligned}
\sum_{i=1}^n \gcd(n,i) &= \sum_{d=1}^n \left ( d\times \sum_{i=1}^n \left [ \gcd(n,i)=d \right ] \right )\\&= \sum_{d\mid n} \left ( d\times \varphi(\frac{n}{d}) \right )
\end{aligned}
\]
拿这题讲讲怎么 \(O(\sqrt{n})\) 在线处理 \(\varphi(x)\)。
::::info[Lemma1]{open}
若 \(p\) 是质数，则有 \(\varphi(p^n)=p^{n-1}(p-1)\)
::::
::::info[Prove1]
在小于等于 \(p^n\) 的正整数中，只有 \(p,2p,3p\cdots,p^{n-1}p\) 不与 \(p^n\) 互质，这样的数有 \(p^{n-1}\) 个。
因此 \(\varphi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)\)
::::
::::info[Lemma2]{open}
若 \(a,b\) 互质，则有 \(\varphi(a)\times \varphi(b)=\varphi(a\times b)\)。（证明 \(\varphi\) 是积性函数）
::::
::::info[Prove2]
待补。
::::
我们考虑把 \(x\) 质因数分解，对于每一组 \(p_i^{k_i}\) 都给答案乘上 \(p_i^{k_i-1}(p_i-1)\)。但因为里面包含了一个 \(x\)，所以还可以接着化简。
\(\varphi(x)=x\times \frac{(p_1-1)(p_2-2)\cdots (p_n-1)}{p_1p_2\cdots p_n}\)
单次复杂度是质因数分解的 \(O(\sqrt{n})\)。
ps：如果你 85pts 记得判是不是完全平方数啊啊啊调了 3h
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
unsigned long long n,yinzi[100005],tot,ans;
inline int phi(int x){int tmp=x;for(int i=2;i<=sqrt(x);i++){if(x%i==0){tmp=tmp/i*(i-1);}while(x%i==0){x/=i;}}if(x>1){tmp=tmp/x*(x-1);}return tmp;
}
signed main(){cin>>n;for(int i=1;i<=sqrt(n);i++){if(n%i==0){yinzi[++tot]=i;if(i*i==n){continue;}yinzi[++tot]=n/i;}}for(int i=1;i<=tot;i++){ans+=yinzi[i]*phi(n/yinzi[i]);}cout<<ans<<endl;return 0;
}