题目

题目链接：https://www.luogu.com.cn/problem/P2158

思路

gcd(x,y)=1的就计入考虑 我们可以寻找gcd(x,y)!=1的 用f[i]记录n-1*n-1里面有多少个公约数为i的数 再减去f[i *k] (k>=2)的值 思想与欧拉定理一致 最后加上x=0y=0的两种情况

代码

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<cctype> #include<ctime> #include<iostream> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<iomanip> #include<list> #include<bitset> #include<sstream> #include<fstream> #include<complex> #include<algorithm> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define ll long long using namespace std; const int INF = 0x3f3f3f3f; int f[100010]; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n; cin>>n; if(n==1) cout<<0<<endl; else{ int res=(n-1)*(n-1); n--; for(int i=n;i>=2;i--){ f[i]=(n/i)*(n/i); for(int j=2;j*i<=n;j++) f[i]-=f[j*i]; res-=f[i]; } cout<<res+2<<endl;} return 0; }