POJ.2407 Relatives

1.Problem
http://poj.org/problem?id=2407

2.Idea
Prime Factorization + Inclusion-exclusion principle

3.Source

 vector<int> a;  
 int n, m;  
 Int gcd(const Int a, const Int b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 void pFac(Int H)  
 {  
      for (Int i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                a.push_back(i);  
           }  
      }  
      if (H > 1) {  
           a.push_back(H);  
      }  
      m = a.size();  
 }  
 void solve()  
 {  
      while (1) {  
           scanf("%lld", &n);  
           if (n == 0) break;  
           a.clear();  
           pFac(n);  
           Int res = 0;  
           for (int i = 1; i < (1 << m); i++) {  
                int num = 0;  
                for (int j = i; j != 0; j >>= 1) {  
                     num += j & 1;  
                }  
                Int lcm = 1;  
                for (int j = 0; j < m; j++) {  
                     if (i >> j & 1) {  
                          lcm = lcm / gcd(lcm, a[j]) * a[j];  
                          if (lcm > n) break;  
                     }  
                }  
                if (num % 2 == 0) res -= n / lcm;  
                else res += n / lcm;  
           }  
           printf("%d\n", n - res);  
      }  
 }