#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<vector>#include<queue>#include<stack>#include<map>#define N 1000100using namespace std;__int64 k;__int64 prime[N],num[N];int t;__int64 IEP(__int64 pn){ /// [n,m]区间求与k互质的个数__int64 pt = 0;__int64 s = 0;num[pt++] = -1;for(__int64 i=0;i<t;i++){__int64 l = pt;for(__int64 j=0;j<l;j++){num[pt++] = num[j]*prime[i]*(-1);}}for(__int64 i=1;i<pt;i++){s += pn/num[i];}return s;}int main(){while(scanf("%I64d",&k)!=EOF){__int64 n = k;__int64 pk = sqrt(k);t = 0;for(int i=2;i<=pk;i++){if(k%i == 0){prime[t++] = i;}while(k%i == 0){k = k/i;}}if(k!=1){prime[t++] = k;}__int64 sum = n – IEP(n);printf("%I64d\n",sum);}return 0;}
，当你能飞的时候就不要放弃飞
