今天给自己加课在机房呆了一天。
因为 2 机房没网所以来了 1 机房，然后一整天写了几道数学题，做了若干之前鸽掉的题，把我洛谷上"尝试过的题目"清了清，现在只剩 6 道了，好像我今天一天写了 27 道题???
哦刚刚又写了一道，28 道了。
别问我为啥只放崩铁的图，因为我只存了这些
这图应该元旦发
给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对。
- 对于 \(100\%\) 的数据，保证 \(1\le n\le10^7\)。
预处理出 \(\phi(n)\) 以内的欧拉函数，然后前缀和。
\[ans=\sum_{d\in prime }2(\sum_{x=1}^{\lfloor \frac n d \rfloor}φ(x))-1
\]
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,l,ans;
const int N=1e7;
int phi[N],prime[N],sum[N];
int cnt;
bool vis[N];
void phigros(int n)
{
phi[1]=1;
for(register int i=2;i<=n;++i)
{
if(!vis[i])
prime[++cnt]=i,phi[i]=i-1;
for(register int j=1;j<=cnt && i*prime[j]<=n;++j)
{
vis[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);
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
phigros(n);
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+phi[i];
for(int i=1;i<=cnt && prime[i]<=n;++i)
ans+=2*sum[n/prime[i]]-1;
cout<<ans;
}
学校物理周测一共 9 个题，一个选择 10 分，一个大题一问 16 分???，提前步入高中物理生活了是吧，少选一个多选直接去世是吧???
然后没啥魔怔事了，继续努力吧。