描述
给一个整数N，请你求出以N为分母的最简(既约)真分数中第K小的是多少？
输入
两个整数N个K。
对于30%的数据，1 <= N <= 1000000
对于100%的数据，1 <= N <= 10000000000 且 1 <= K <= φ(N)。其中φ(N)是欧拉函数，也即1~N中与N互质的数的个数。
输出
一个整数表示答案的分子
样例输入
100 10
样例输出
23
思路：
显然和欧拉函数关系不大。。。开始思路已经很接近了。分解质因子，然后二分1到Mid中与分母不互质的有多少（容斥去重）。有想到唯一分解，但是没有想到最多可以分解为多少个，万一是上万呢？然而最多可以分解为两位数个质因子，假设有2，3，5，，，(n个)，则2*3*5*....*>2^n，n=10就大的不得了。
- 1到x有因子y的树的个数为x/y个。
- 容斥定理去重。
#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 ;
}