水题
euler 是直接判断
euler2 是欧拉筛
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define MAXN 1005 #define MOD (int)1e9+7 #define PI acos(-1.0) #define DINF (1e10) #define LINF ((1LL)<<50) #define INF (0x3f3f3f3f) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define line cout<<"--------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #define FOUT freopen("out.txt","w",stdout) #pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL; // typedef unsigned long long ULL; typedef __int64 LL; // typedef unisigned __int64 ULL; // LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; } // LL lcm(LL a,LL b){ return a*b/gcd(a,b); } /********************* F ************************/ int euler(LL n){ int x = n; int phi = n; for(int i = 2 ; i*i <= n ; i++){ if(x % i == 0){ phi = phi / i * (i-1); while(x % i == 0) x /= i; } } if(x != 1) phi = phi / x * (x-1); return phi; } int phi[100001]; void euler2() { phi[1] = 1; for(int i = 2; i <= 100000; i++){ if(!phi[i]){ for(int j = i; j <= 100000; j += i){ if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } } } int main() { //FIN; //FOUT; LL n; while(~scanf("%I64d",&n) && n){ printf("%d ",euler(n)); } return 0; }