POJ 2773 Happy 2006#素数筛选+容斥原理+二分

http://poj.org/problem?id=2773

说实话这道题。。一点都不Happy好吗

似乎还可以用欧拉函数来解这道题,但正好刚学了容斥原理和二分,就用这个解法吧。

题解:要求输出[1,m]中与m互质的第k个数,先打表,找到m的所有质因数,然后用二分实现,最开始区间为[1,2^60],利用容斥原理去找区间[1,mid]内素数的个数t,不断进行二分,直到所查找的区间[l,r]内素数的个数t等于k,mid=l=r,则此时的l就是第k个与m互质的数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define N 1000005 vector<int> v;
void getPrime(int n) //[l,r]内与n互素的数字个数
{
v.clear();
//筛选素数
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
v.push_back(i);
while(n%i==0)
n/=i;
}
}
if(n>1)
v.push_back(n);
} ll solve(ll n)
{
//容斥原理的二进制解法
int len=v.size();
ll res=0;
for(int i=1;i<(1<<len);i++)
{
int cnt=0;
ll val=1;
for(int j=0;j<len;j++)
{
if(i&(1<<j))
{
cnt++;
val*=v[j];
}
}
if(cnt&1) //若为奇数项进行加法,偶数项进行减法
res+=n/val;
else res-=n/val;
}
return n-res;
} int main()
{
int m,K;
while(~scanf("%d%d",&m,&K))
{
getPrime(m);
ll l=1,r=(1ll<<60),mid,t;
while(l<r)
{
mid=((l+r)>>1);
t=solve(mid);
if(t>=K)
r=mid;
else l=mid+1;
}
printf("%I64d\n",l);
}
return 0;
}
上一篇:[chrome插件] 利滚利计算器 银行存款 基金理财 余额宝收益计算


下一篇:iOS 模拟器上录制Demo视频