第k互素数

【原题链接】

【题意说明】

计算与m和n都互为素数的数中第k大的数，假如X与Y互为素数，那么X和Y的最大公约数必为1。

【问题分析】

本题要用到容斥原理！相关题目有：Redraiment猜想、找新朋友。不过前面一直都是TL！后面得到了提示：再利用二分即可求出！

（1）首先求出m、n的素数因子，并对这些素数因子进行排序；

（2）从1~10^12（这个数可以估算出来）二分，再利用容斥原理求其中间的数所得的互为素数的个数！若少则二分右侧，否则二分左侧。

最后求得结果！

容斥原理求数部分代码：

View Code

 1 void find(int x, __int64 y, int t){
 2      int i;
 3      for (i=x;i<total;i++)
 4          if (prime[i]<=y)
 5          {
 6             s+=t*y/prime[i];
 7             find(i+1, y/prime[i], -t);
 8          }
 9          else break;
10 }

二分求值部分代码：

View Code

1      __int64 l=1,r=Max,mid;
2      while (l<=r){
3            s=0;mid=(l+r)>>1;
4            find(0,mid,1);
5            if(mid<s+k)l=mid+1;
6            else r=mid-1;
7      } 
8      if(mid<s+k)mid++;