[二分+容斥原理] poj 2773 Happy 2006

题目链接：

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

2006 1
2006 2
2006 3

1
3
5

[Submit]   [Go Back]   [Status]   [Discuss]

题目意思：

求与m互质的第k大的数

解题思路：

二分+容斥原理

二分出要求的数i,用容斥原理求出1~i之间的与m互质的数的个数kk,如果kk<k扩大范围，如果kk>k扩大范围，如果kk=k并且gcd(i,m)=1说明刚好找到，否则继续缩小范围。

代码：

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define N 1000
bool isp[N+10];
int pri[N+10],pp[N+10],cnt,cnt0;
int m,k;
ll res;

void init()  //打出1000内的质数
{
    cnt=0;
    for(int i=1;i<=N;i++)
        isp[i]=true;

    for(int i=2;i<=N;i++)
    {
        if(isp[i])
        {
            pri[++cnt]=i;
            for(int j=i*2;j<=N;j+=i)
                isp[j]=false;
        }
    }
}
void Cal(int cur) //对cur分解质因数
{
    cnt0=0;

    for(int i=1;pri[i]*pri[i]<=cur;i++)
    {
        if(!(cur%pri[i]))
        {
            pp[++cnt0]=pri[i];
            while(!(cur%pri[i]))
                cur/=pri[i];
        }
    }
    if(cur!=1)
        pp[++cnt0]=cur;
}

void dfs(ll hav,int cur,int num,ll va) //容斥原理求出与m互质的且小于va的数的个数
{
    if(cur>cnt0||(hav>va))
        return ;
    for(int i=cur;i<=cnt0;i++)
    {
        ll temp=hav*pp[i];

        if(num&1)
            res-=va/temp;
        else
            res+=va/temp;
        dfs(temp,i+1,num+1,va);
    }
}
void solve(ll cur) //求出1~cur间与m互质的数的个数
{
    res=cur;

    for(int i=1;i<=cnt0;i++)
    {
        res-=cur/pp[i];
        dfs(pp[i],i+1,2,cur);
    }
}
ll gcd(ll a,ll b) //求最大公约数
{
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   init();
   while(~scanf("%d%d",&m,&k))
   {
       ll ans,l,r,mid;

       l=1,r=(1LL<<62LL); //初始化一个很大的数
       Cal(m);

       while(l<=r)
       {
           mid=(l+r)>>1;
           solve(mid);
           ll temp=res; //个数

           //printf("mid:%I64d res:%I64d\n",mid,res);
           //system("pause");

           if(temp<k) //放大
                l=mid+1;
           else if(temp==k)
           {
               if(gcd(mid,m)==1) //最后一个刚好是与m互质的，说明恰好找到
               {
                   ans=mid;
                   break;
               }
               r=mid-1; //否则继续缩小
           }
           else
                r=mid-1;
       }
       printf("%I64d\n",ans);
   }
   return 0;
}

[二分+容斥原理] poj 2773 Happy 2006,,5-wow.com