洛谷:https://www.luogu.org/problemnew/show/P2158
bzoj:problem 2190
这题就是一道欧拉函数板子题。
对gcd稍微有点了解的人就会知道,在一个方格里,两个点的横纵坐标差的gcd为1时中间不会经过任何格点。
gcd=1,也就是说两个数互质呗,自认而然的就想到了欧拉函数。
我们枚举每一列,统计欧拉函数值。
这里要注意的是,例如(4,3)这个点符合要求时,(3,4)这个点也符合要求,然而我们统计3这个点的函数值时,并没有统计,所以我们对于每一列的函数值乘2,会在第一列多计算一个点,所以答案需要-1.
还有一个特判,为啥就不说了。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> using namespace std; int n,ans; int prime[40006],tot,phi[40006]; bool vis[40006]; void get_phi() { 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&&prime[j]*i<=n;j++) { vis[prime[j]*i]=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]]; } } } int main() { scanf("%d",&n); if(n==1){ cout<<"0"; return 0; } n--; get_phi(); // for(int i=1;i<=n;i++)cout<<phi[i]<<" ";cout<<" "; for(int i=1;i<=n;i++)ans+=phi[i]*2; printf("%d",ans+1); }