POJ 2773 Happy 2006 (公式法 or 二分容斥定理)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
http://poj.org/problem?id=2773
首先看一个简单的方法：
若K<=phi(n)，直接暴力计算即可；
若K>phi(n)，我们可以利用gcd(k'+λn,n)=gcd(k',n)，将其转化为K<=phi(n)的情况，
具体代码如下：
/*2355ms,3504KB*/
#include <cstdio>
const int maxn = 1000005;
int num[maxn];
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int main()
{
int n, k;
while (~scanf("%d%d", &n, &k))
{
int cnt = 0;
for (int i = 1; i <= n; i++)
if (gcd(n, i) == 1) num[++cnt] = i;
int t = k % cnt, p = k / cnt;
if (t == 0) t = cnt, p--;
printf("%d\n", num[t] + n * p);
}
return 0;
}但是这个方法太慢了，更快的方法如下：
首先处理出n的质因子集合{p1,p2,p3,...}
然后从另一个角度看K：
对于一个数num，若将其p1的倍数划去，p2的倍数划去，p3的倍数划去，…，最后若恰好剩下K个数，这个num就是我们要找的数。
我们可以二分找num，但要注意的是，可能有两个不同的num，它们在划去pi后都剩下K个数，这时我们要取小的那个数。
而计算剩下的数的个数，可以用容斥定理搞定。
完整代码：
/*0ms,372KB*/
#include<cstdio>
const int mx = 1005;
const int MAX = 1000000000;
bool vis[mx];
int prime[mx], a[11], cnt, cnt_n;
void init()
{
for (int i = 2 ; i < mx; i++)
if (!vis[i])
{
prime[cnt++] = i;
for (int j = i * i ; j < mx; j += i)
vis[j] = true;
}
}
/// O(log n)求n的所有质因子,不超过10个
void getprime(int n)
{
cnt_n = 0;
for (int i = 0; i < cnt && prime[i] * prime[i] <= n; i++)
if (n % prime[i] == 0)
{
a[cnt_n++] = prime[i];
while (n % prime[i] == 0)
n /= prime[i];
}
if (n > 1) a[cnt_n++] = n;
}
/// 计算划去pi的倍数后剩下的数的个数
int left(int num)
{
int sum = 0;///划去的数的个数
for (int i = 1; i < (1 << cnt_n); i++) /// 注意cnt_n的个数与log n差不多(一般不超过10)，所以可以用位运算
{
int tmp = 1, one = 0;
for (int j = 0; j < cnt_n; j++)
if ((1 << j) & i)
{
one++;///i的二进制中1的个数
tmp *= a[j];
}
if (one & 1) sum += num / tmp;
else sum -= num / tmp;
}
return num - sum;
}
int main()
{
init();
int n, K;
while (~scanf("%d%d", &n, &K))
{
getprime(n);
int l = 1, r = MAX, mid, ans;
while (l <= r)
{
mid = (l + r) >> 1;
int pt = left(mid);
if (pt >= K)
{
if (pt == K) ans = mid; /// 但这可能不是真正的答案，还要看看有没有更小的数也满足条件
r = mid - 1;
}
else l = mid + 1;
}
printf("%d\n", ans);
}
return 0;
}| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |