POJ 2773 Happy 2006 二分+容斥原理
2012-08-05 13:03:00

[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cmath>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
typedef long long LL;
const int N = 1000010;
int prime[N/2], flag[N],cntprime = 0;
int num1[110],num2[110],cntnum;
bool use[110];
LL base;
void init(){
CLR(flag,0);
for(int i = 2; i <= sqrt(N+0.5); ++i){
if(!flag[i]){
for(int j = i * 2; j <= N; j += i){
flag[j] = 1;
}
}
}
for(int i = 2;i <= N; ++i){
if(!flag[i])
prime[cntprime++] = i;
}

void fun(int x){
for(int i = 0; i < cntprime; ++i){
if(x % prime[i] == 0){
num1[cntnum++] = prime[i];
while(x % prime[i] == 0){
x /= prime[i];
}
}
}

void dfs(int begin,int id,int cnt,LL &x){
if(id == cnt){
LL ans = 1;
for(int i = 0;i < id; ++i){
ans *= num2[i];
}
if(id % 2){
x = x - base/ans;
}
else{
x = x + base/ans;
}
return;
}
for(int i = begin;i < cntnum; ++i){
if(!use[i]){
use[i] = true;
num2[id] = num1[i];
dfs(i,id+1,cnt,x);
use[i] = false;
}
}

LL cal(LL x){
base = x;
for(int i = 1; i <= cntnum; ++i){
CLR(use,false);
CLR(num2,0);
dfs(0,0,i,x);
}
return x;

LL binary_search(int n,int K){
LL rp = 10000000000;
LL lp = 1;
while(lp <= rp){
LL mid = lp + (rp - lp) / 2;
LL nummid = cal(mid);
if(K < nummid){
rp = mid - 1;
}
else if(K > nummid){
lp = mid + 1;
}
else{
return mid;
}
}

int main(){
//freopen("1.txt","r",stdin);
init();
int n,K;
while(scanf("%d%d",&n,&K) != EOF){
CLR(num1,0);
CLR(num2,0);
cntnum = 0;
fun(n);
LL ans = binary_search(n,K);
while(1){
LL xx = cal(ans-1);
if(xx == K)
ans--;
else
break;
}
printf("%lld\n",ans);
}
return 0;