频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 2773 Happy 2006 二分+容斥原理
2012-08-05 13:03:00           
收藏   我要投稿
题意:就是给你一个数n和k,求和n互质的第k个数。
思路:一道容斥原理的题目,用容斥原理我们可以求出一个范围内和n互质的数有多少个,但是不能确定第几个是多少。这时候可以用二分求出答案,因为前K+1个数内和n互质的数一定大于等于前K个数和n互质的数的个数,即随着K的增加,和n互质的数的个数是递增的。所以可以用二分求答案,由于k比较大,所以二分的上限应该足够大。二分求出后还有一个问题,因为里面有一些数是相同的,所以我们二分求出的答案不一定是第一个出现的,这时候还需要向前循环处理一下,最后就可以得到答案。
代码:
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <string.h> 
#include <cmath> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
typedef long long LL; 
const int N = 1000010; 
int prime[N/2], flag[N],cntprime = 0; 
int num1[110],num2[110],cntnum; 
bool use[110]; 
LL base; 
void init(){ 
    CLR(flag,0); 
    for(int i = 2; i <= sqrt(N+0.5); ++i){ 
        if(!flag[i]){ 
          for(int j = i * 2; j <= N; j += i){ 
            flag[j] = 1; 
          } 
        } 
    } 
    for(int i = 2;i <= N; ++i){ 
      if(!flag[i]) 
          prime[cntprime++] = i; 
    } 

void fun(int x){ 
    for(int i = 0; i < cntprime; ++i){ 
        if(x % prime[i] == 0){ 
          num1[cntnum++] = prime[i]; 
          while(x % prime[i] == 0){ 
            x /= prime[i]; 
          } 
        } 
    } 

void dfs(int begin,int id,int cnt,LL &x){ 
    if(id == cnt){ 
      LL ans = 1; 
      for(int i = 0;i < id; ++i){ 
        ans *= num2[i]; 
      } 
      if(id % 2){ 
           x = x - base/ans; 
      } 
      else{ 
          x = x + base/ans; 
      } 
      return; 
    } 
    for(int i = begin;i < cntnum; ++i){ 
        if(!use[i]){ 
          use[i] = true; 
          num2[id] = num1[i]; 
          dfs(i,id+1,cnt,x); 
          use[i] = false; 
        } 
    } 

LL cal(LL x){ 
    base = x; 
    for(int i = 1; i <= cntnum; ++i){ 
        CLR(use,false); 
        CLR(num2,0); 
        dfs(0,0,i,x); 
    } 
    return x; 

LL binary_search(int n,int K){ 
    LL rp = 10000000000; 
    LL lp = 1; 
    while(lp <= rp){ 
      LL mid = lp + (rp - lp) / 2; 
      LL nummid = cal(mid); 
      if(K < nummid){ 
        rp = mid - 1; 
      } 
      else if(K > nummid){ 
        lp = mid + 1; 
      } 
      else{ 
        return mid; 
      } 
    } 

int main(){ 
    //freopen("1.txt","r",stdin); 
    init(); 
    int n,K; 
    while(scanf("%d%d",&n,&K) != EOF){ 
      CLR(num1,0); 
      CLR(num2,0); 
      cntnum = 0; 
      fun(n); 
      LL ans = binary_search(n,K); 
      while(1){ 
        LL xx = cal(ans-1); 
        if(xx == K) 
            ans--; 
        else 
            break; 
      } 
      printf("%lld\n",ans); 
    } 
    return 0; 


作者:wmn_wmn
点击复制链接 与好友分享!回本站首页
相关TAG标签 原理 容斥
上一篇:HDU OJ 2586 How far away ?[LCA的Tarjan离线算法]
下一篇:HDU 4335 What is N? 多校4(数论)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站