hdu3388Coprime 二分+容斥原理 - c++编程基础

TOP

hdu3388Coprime 二分+容斥原理

2015-11-21 01:00:24 来源: 作者: 【大中小】浏览:3次

//找第k个和n，m互质的数
//由容斥原理可得
//在[1,x]范围内且与n不互质的数的个数为：
//对于所有的n的素数因子：和一个素数因子不互质的个数-两个素数因子相乘的个数+三个素数因子相乘的个数-.....
//对于x越大，在[1 , x]范围内的与n,m互质的数越多，所以存在单调性，可以用二分找到刚好有k个数和n,m互质
#include
#include
#include
#include
using namespace std ;
typedef __int64 ll ;
const int maxn = 100010 ;
const int inf = 1e9 ;
map ma ;
ll p[maxn] ;
int len ;
void getprime(ll n)
{
for(int i = 2;i*i <= n;i++)
{
if(n%i == 0 && !ma[i])
{
p[++len] = i ;
ma[i] = 1;
}
while(n%i == 0)n/=(ll)i ;
}
if(n > 1 && !ma[n]){p[++len] = n;ma[n]=1;}
}
ll dfs(int pos , ll n)
{
ll ans = 0 ;
for(int i = pos ;i <= len ;i++)
ans += n/p[i] - dfs(i+1 , n/p[i]) ;
return ans ;
}
ll find(ll l , ll r , ll num )
{
while(l <= r)
{
ll mid = (l+r) >> 1 ;
if((mid - dfs(1 , mid)) < num)
l = mid + 1 ;
else r = mid - 1;
}
return l ;
}
int main()
{
// freopen("in.txt","r",stdin) ;
// freopen("out.txt","w" ,stdout) ;
int T ;int cas = 0 ;
int n , m ;int k ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%d%d%d" ,&n , &m , &k) ;
len = 0 ;
ma.clear() ;
getprime((ll)(n));
getprime((ll)(m));
ll ans = find(1 , (ll)inf*(ll)inf, (ll)k);
printf("Case %d: " , ++cas) ;
printf("%I64d\n" , ans) ;
}
return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu5242 上海邀请赛优先队列+贪心	下一篇：算法导论--动态规划（钢条切割）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: