本文共 1227 字,大约阅读时间需要 4 分钟。
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 9987 | Accepted: 3434 |
Description
Input
Output
Sample Input
2006 12006 22006 3
Sample Output
135
解题思路:二分枚举1-2^64之间的数x,找到1-x与m互质的个数s,这里利用容斥原理,如果s与k相等,那么该x即为结果;
参考代码:
#include#include #include using namespace std;typedef long long ll;const int MAX = 1000010;int p[MAX],count;void fun(ll n){ ll i; count=0; for (i=2;i*i<=n;i++){ if (n%i==0){ p[count++]=i; while (n%i==0) n/=i; } } if (n>1) p[count++]=n;}ll solve(ll n,ll r){ ll sum=0; for (int i=1;i<(1< >n>>m){ fun(n); ll r=0xffffffff,l=1; while (r-l>0){ mid=(r+l)/2; num=solve(n,mid); if (num>=m) r=mid; else l=mid+1; } cout< <
转载地址:http://efbqb.baihongyu.com/