描述
给一个整数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[2000],b[2000],tot;//a是因子乘积，b是代表奇偶。 ll K,N,l,r,Mid,ans; ll prim[20],cnt; void dfs(ll x,ll y,ll num) { if(y==cnt+1){ if(x==1) return ; a[++tot]=x;b[tot]=num&1?1:-1;return; } dfs(x*prim[y],y+1,num+1); dfs(x,y+1,num); } void divide(ll x) { ll y=x; for(ll i=2;i*i<=x;i++){ if(y%i==0) prim[++cnt]=i; while(y%i==0&&y) y/=i; } if(y>1) prim[++cnt]=y;//唯一分解之后的剩余，可以肯定是个质数，自己反正吧。 dfs(1,1,0); } bool check(ll x) { ll num=0; for(int i=1;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=1;r=10000000001; while(l<=r){ Mid=(l+r)>>1; if(check(Mid)){ ans=Mid; r=Mid-1; } else l=Mid+1; } printf("%lld ",ans); return 0; }