POJ 2773 Happy 2006

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 const LL INF = 0x3f3f3f3f3f3f3f3f;
 7 const int maxn = 50;
 8 int p[maxn],tot;
 9 void init(int x){
10     tot = 0;
11     for(int i = 2; i*i <= x; ++i){
12         if(x%i == 0){
13             p[tot++] = i;
14             while(x%i == 0) x /= i;
15         }
16     }
17     if(x > 1) p[tot++] = x;
18 }
19 LL solve(LL x){
20     LL ret = 0;
21     for(int i = 1; i < (1<<tot); ++i){
22         int cnt = 0,tmp = 1;
23         for(int j = 0; j < tot; ++j){
24             if((i>>j)&1){
25                 ++cnt;
26                 tmp *= p[j];
27             }
28         }
29         if(cnt&1) ret -= x/tmp;
30         else ret += x/tmp;
31     }
32     return x + ret;
33 }
34 int main(){
35     int n,k;
36     while(~scanf("%d%d",&n,&k)){
37         LL ret = 0,low = 1,high = INF;
38         init(n);
39         while(low <= high){
40             LL mid = (low + high)>>1;
41             if(solve(mid) >= k){
42                 ret = mid;
43                 high = mid - 1;
44             }else low = mid + 1;
45         }
46         printf("%I64d\n",ret);
47     }
48     return 0;
49 }