百万小小兵 (HGOI 2019.2.17 T1)

## 题目大意 求1~n与n不互质的数的个数 ## 数据范围 n<=10000000 ### 解法 很简单，很无脑 求一下欧拉函数，减一下就好了 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int Ola(int x) { int res=x,k=x; for(int i=2;i*i<=x;i++) if(k%i==0) { res=res/i*(i-1); while(k%i==0) k/=i; } if(k>1) res=res/k*(k-1); return res; } int main() { scanf("%d",&n); printf("%d",n-Ola(n)); return 0; } ```