題意：就是給你一個數n和k，求和n互質的第k個數。
思路：一道容斥原理的題目，用容斥原理我們可以求出一個范圍內和n互質的數有多少個，但是不能確定第幾個是多少。這時候可以用二分求出答案，因為前K+1個數內和n互質的數一定大於等於前K個數和n互質的數的個數，即隨著K的增加，和n互質的數的個數是遞增的。所以可以用二分求答案，由於k比較大，所以二分的上限應該足夠大。二分求出後還有一個問題，因為裡面有一些數是相同的，所以我們二分求出的答案不一定是第一個出現的，這時候還需要向前循環處理一下，最後就可以得到答案。
代碼：
[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;
}
作者：wmn_wmn
