描述

给一个整数N，请你求出以N为分母的最简(既约)真分数中第K小的是多少？

输入

两个整数N个K。

对于30%的数据，1 <= N <= 1000000

对于100%的数据，1 <= N <= 10000000000 且 1 <= K <= φ(N)。其中φ(N)是欧拉函数，也即1~N中与N互质的数的个数。

输出

一个整数表示答案的分子

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

ll a[],b[],tot;//a是因子乘积，b是代表奇偶。

ll K,N,l,r,Mid,ans;

ll prim[2],cnt;

void dfs(ll x,ll y,ll num)

{

    if(y==cnt+){

       if(x==) return ;

       a[++tot]=x;b[tot]=num&?:-;return;

    }

    dfs(x*prim[y],y+,num+);

    dfs(x,y+,num);

}

void divide(ll x)

{

    ll y=x;

    for(ll i=;i*i<=x;i++){

        if(y%i==) prim[++cnt]=i;

        while(y%i==&&y) y/=i;

    }

    if(y>) prim[++cnt]=y;//唯一分解之后的剩余，可以肯定是个质数，自己反正吧。

    dfs(,,);

}

bool check(ll x)

{

    ll num=;

    for(int i=;i<=tot;i++){

        num+=x/a[i]*b[i];

    }

    if(x-num>=K) return true;

    return false;

}

int main()

{

    scanf("%lld%lld",&N,&K);

    divide(N);l=;r=;

    while(l<=r){

        Mid=(l+r)>>;

        if(check(Mid)){

            ans=Mid; r=Mid-;

        }

        else l=Mid+;

    }

    printf("%lld\n",ans);

    return ;

}