# POJ 2773 Happy 2006（容斥原理+二分）

Happy 2006

Time Limit: 3000MS

Memory Limit: 65536K

Total Submissions: 10827

Accepted: 3764

Description

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006.  Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.

Input

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).

Output

Output the K-th element in a single line.

Sample Input

```2006 1
2006 2
2006 3```

Sample Output

```1
3
5```
`这道题目是HDU 3388的简化版，方法几乎一模一样`
`http://blog.csdn.net/dacc123/article/details/51285731`
```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const LL INF=(LL)1<<62;
#define MAX 1000000
LL prime[MAX+5];
LL sprime[MAX+5];
LL q[MAX+5];
LL check[MAX+5];
LL m,k,cnt;
void eular()
{
memset(check,false,sizeof(check));
int tot=0;
for(int i=2;i<=MAX+5;i++)
{
if(!check[i])
prime[tot++]=i;
for(int j=0;j<tot;j++)
{
if(i*prime[j]>MAX+5) break;
check[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
void Divide(LL n)
{
cnt=0;
LL t=(LL)sqrt(1.0*n);
for(LL i=0;prime[i]<=t;i++)
{
if(n%prime[i]==0)
{
sprime[cnt++]=prime[i];
while(n%prime[i]==0)
n/=prime[i];
}
}
if(n>1)
sprime[cnt++]=n;
}
LL Ex(LL n)
{
LL sum=0,t=1;
q[0]=-1;
for(LL i=0;i<cnt;i++)
{
LL x=t;
for(LL j=0;j<x;j++)
{
q[t]=q[j]*sprime[i]*(-1);
t++;
}
}
for(LL i=1;i<t;i++)
sum+=n/q[i];
return sum;
}
LL binary()
{
LL l=1,r=INF;
LL mid,ans;
while(l<=r)
{
mid=(l+r)/2;
if((mid-Ex(mid))>=k)
{
r=mid-1;
}
else
l=mid+1;
}
return l;
}
int main()
{
eular();
while(scanf("%lld%lld",&m,&k)!=EOF)
{
if(m==1)
{
printf("%lld\n",k);
continue;
}
Divide(m);
printf("%lld\n",binary());
}
return 0;
}```

0 条评论

• ### HDU 3388 Coprime（容斥原理+二分）

Coprime Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

• ### HDU 4059 The Boss on Mars（容斥原理）

The Boss on Mars Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/...

• ### HDU 5667 Sequence（矩阵快速幂）

Problem Description Holion August will eat every thing he has found. Now t...

• ### 打表法——暴力破解方法之一

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~

• ### 洛谷 P1313 计算系数

题目描述 给定一个多项式 ，请求出多项式展开后 项的系数。 输入输出格式 输入格式： 输入文件名为factor.in。 共一行，包含5 个整数，分别为 a...

• ### 11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫，如果遇到一个不合法的点\(i\)，那么升级\(i + R\)处的炮台。。

• ### 扩展中国剩余定理详解

前言 阅读本文前，推荐先学一下中国剩余定理。其实不学也无所谓，毕竟两者没啥关系 扩展CRT 我们知道，中国剩余定理是用来解同余方程组 但是有一个非常令...

• ### 『数学』--数论--组合数+卢卡斯定理+扩展卢卡斯定理

卢卡斯定理： 求 C ...

• ### 2057. [ZLXOI2015]殉国

输入文件：BlackHawk.in   输出文件：BlackHawk.out 评测插件 时间限制：0.05 s   内存限制：256 MB 【题目描述】 ...

• ### 洛谷P3383 【模板】线性筛素数(Miller_Rabin)

题目描述 如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入输出格式 输入格式： 第一行包含两个正整数N、M，分别表示...