庆祝一下：数论紫题达成成就！
第一道数论紫题。写个题解庆祝一下吧。
简要题意：求
\[\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)==p]
\]
\]
其中 \(p\) 为素数。
注：
$ [A] = 0 $ 当且仅当 \(A\) 不成立。 $ [A] = 1 $ 当且仅当 \(A\) 成立。
这不就是单位函数的定义嘛。
先抛个定义：
\[f_n = \sum_{i=1}^n [\gcd(i,n) == 1]
\]
\]
即 \(\leq n\) 且 与 \(n\) 互质 的数的个数。
下面开始推式子：
愉快地推式子时间
\[\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j) == p]
\]
\]
\[= \sum_{p=1}^n \sum_{i=1}^{\lfloor \frac{n}{p} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{p} \rfloor} [\gcd(i,j) == 1]
\]
\]
（依据：将素数 \(p\) 独立展开，枚举它们的最大公因数值）
\[= \sum_{p=1}^n \bigg ( \sum_{i=1}^{\lfloor \frac{n}{p} \rfloor} \bigg( 2 \times \sum_{j=1}^i [\gcd(i,j) == 1] \bigg ) - 1 \bigg )
\]
\]
（依据：考虑 \(i \leq j\) 的情况，然后 \(\times 2\) ，对于 \(i = j\) 的情况，\(-1\) 可以很好地解决）
\[= \sum_{p=1}^n \bigg ( \bigg ( 2 \times \sum_{i=1}^{\lfloor \frac{n}{p} \rfloor} f_i \bigg ) - 1 \bigg )
\]
\]
如果我们用 \(O(n)\) 的时间求出了所有的 \(f_i\) 和 \(\leq n\) 所有的素数，那么直接 做 \(f\) 的前缀和 ，扫一遍完事。
求出所有的 \(f_i\) ：显然线性筛模板。（当然是 欧拉筛），然后顺便可以求出所有的素数。
时间复杂度： \(O(n)\).
实际得分：\(100pts\).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,phi[N],prime[N];
int f=0; bool h[N];
ll ans=0,sum[N];
// phi[i] 就是 <= n 的与 n 互质的数的个数
// prime[i] 为第 i 个素数
// h[i] = (i 是素数) ？ 0 : 1
// sum[i] = phi[1] + phi[2] + ... + phi[i]
int main(){
n=read();
phi[1]=1; h[1]=1;
for(int i=2;i<=n;i++) {
if(!h[i]) prime[++f]=i,phi[i]=i-1;
for(int j=1;j<=f && i*prime[j]<=n;j++) {
h[i*prime[j]]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
} //欧拉筛模板
} for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i]; //前缀和
for(int i=1;i<=f && prime[i]<=n;i++)
ans+=(sum[n/prime[i]]<<1)-1; //套式子
printf("%lld\n",ans);
return 0;
}