poj-2773(数论+容斥原理+二分)

我不是女神ヾ 2022-06-10 09:40 186阅读 0赞

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

题目题意：题目给你一个m，让你找第k个与m互质的数(从1开始)

题目分析:可能是上个星期做容斥原理的原因，我看到这个题目的第一反应，一个数与m互质，那么它们没有公共质因子，而确定n之内与m互质的个数，就是利用容斥原理来求得，而这个n的确立，我们就需要利用二分了。

我们打一张素数表，把m分解，然后二分找n,通过容斥原理来求n之内与m互质的个数，来不断更新n。

关于容斥原理这段代码，解释一哈:

将m分解,假设p1,p2,,,pn为m的质因子，那么n之内能被p1整除的个数n/p1,,同理可得能被pn整除的个数为n/pn，但是有很多的重复比如6被2整除，也被3整除。

所以这种计数问题，容斥原理可以很好解决。

n-(n/pk  (1<=k<=n))+(n/pk1pk2   (1<=k1,k2<=n))  -   (n/pk1pk2pk3 (1<=k1,k2,k3<=n))+.......-.........

奇数减，偶数加

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const long long inf=1e14;
    const int maxn=1e6+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    int m,k;
    ll ans;
    void get_prime()//素数打表
    {
        memset (vis,true,sizeof (vis));
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    
    int factor[1000],fcnt;
    void get_factor(int n)//分解m
    {
        memset (factor,0,sizeof (factor));
        fcnt=0;
        for (int i=0;i<cnt&&prime[i]<=n;i++) {
            if (n%prime[i]==0) {
                    factor[fcnt++]=prime[i];
                while (n%prime[i]==0) {
                    n=n/prime[i];
                }
            }
        }
        if (n!=1) {
            factor[fcnt++]=n;
        }
    }
    void dfs (int cur,int num,ll sum,ll n)//利用dfs来实现容斥原理
    {
        ll res=n/sum;
        if (num&1)//奇数减，偶数加
            ans+=res;
        else
            ans-=res;
        for (int i=cur+1;i<fcnt;i++)
            dfs (i,num+1,sum*factor[i],n);
    
    }
    ll solve (ll n)//容斥原理
    {
        ans=0;
        for (int i=0;i<fcnt;i++)
            dfs (i,1,factor[i],n);
        return n-ans;
    }
    int main()
    {
        get_prime();
        while (scanf("%d%d",&m,&k)!=EOF) {
            get_factor(m);
            ll r,l,mid;
            l=1,r=inf;
            while (r-l>=0) {//二分找n
                mid=(r+l)/2;
             //   cout<<l<<" "<<r<<endl;
                if (solve(mid)>=(ll)k) r=mid-1;
                else l=mid+1;
            }
            printf("%lld\n",l);
        }
        return 0;
    }