所以洛谷两道这样的题,另一道要用MI?
考虑每个质数对答案的贡献
如果有(gcd(a,b)=p),则显然(gcd(frac{a}{p},frac{b}{p})=1)
所以每个(p)对答案的贡献就是(sum_{i=1}^{lfloorfrac{n}{p} floor}sum_{j=1}^{lfloorfrac{n}{p} floor}[gcd(i,j)=1])
若(i>j),对于每个(i),贡献为((sum_{j=1}^{i-1}[gcd(i,j)=1])=varphi[i])
对于(i<j)的情况也是一样的,也就是每个单独的(j)贡献为(varphi[j])
若(i=j),则有(1)的贡献
最终答案即为((sum_{i=1}^{m}sum_{j=1}^{lfloor {n/p_i} floor}varphi[j])+m(m)为质数个数,(p_i)为第(i)个质数())
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#define LL long long
#define il inline
#define re register
using namespace std;
const LL mod=1000000007;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL n,phi[10000010],ans;
int prm[1000010],tt;
char v[10000010];
il void init()
{
phi [1] = 1;
for(re int i=2;i<=n;i++)
{
if(!v[i]) prm[++tt]=i,phi[i]=i-1;
for(re int j=1;j<=tt&&i*prm[j]<=n;j++)
{
v[i*prm[j]]=1,phi[i*prm[j]]=phi[i]*(prm[j]-1);
if(i%prm[j]==0) {phi[i*prm[j]]+=phi[i];break;}
}
}
}
il void work()
{
for(re int i=1;i<=n;i++) phi [i] + = phi [i-1];
for(re int i=1;i<=tt;i++) ans+=phi[n/prm[i]];
printf("%lld
",(ans<<1)-tt); //知道为什么是-而不是+吗? 嘿嘿嘿
}
int main()
{
n=rd();
init();
work();
return 0;
}