POJ2773(容斥原理)

Happy 2006

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 11458		Accepted: 4001

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
思路：若a与m互素,那么a+t*m(t>=1)与m 也互素,否则不互素.设小于m且与m互素的数有n个,分别为a(0),a(1),a(2),...,a(n-1).那么第n+1个为a0+m,第n+2个为a(1)+m...第k个为m*(k-1)+a((k-1)%n);

#include <cstdio>
using namespace std;
const int MAXN=1000005;
int m,k;
int relative[MAXN],top;
int gcd(int a,int b)
{
    if(b==0)    return a;
    else return gcd(b,a%b);
}
void sieve()
{
    for(int i=1;i<=m;i++)
    {
        if(gcd(i,m)==1)
        {
            relative[top++]=i;
        }
    }
}
int main()
{
    while(scanf("%d%d",&m,&k)!=EOF)
    {
        top=0;
        sieve();
        int n=(k-1)/top;
        int z=(k-1)%top;
        int res=n*m+relative[z];
        printf("%d
",res);
    }
    return 0;
}

容斥原理+二分.

容斥原理介绍:http://baike.baidu.com/link?url=H0UEe3zE2jUT7Ree_tycNyXcLYRWH4v25KpCZ3DOcx2HN0jaMYB3rJNF45SFs_EDxWo01C0LCz1rrh-_CG4On_

n/p表示1~n中是p倍数的数的个数。求1~m中与n互素的数的个数。先将n进行质因数分解,然后通过位运算枚举所有质因数的组合。若选了奇数个质因数ans+=m/质因数之积，否则ans-=m/质因数之积。然后二分枚举m的范围,确定k.

#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
LL sieve(LL n,LL m)
{
    vector<LL> divisor;
    for(LL i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            divisor.push_back(i);
            while(n%i==0)    n/=i;
        }
    }
    if(n>1)    divisor.push_back(n);
    LL ans=0;
    for(LL mark=1;mark<(1<<divisor.size());mark++)
    {
        LL mul=1;
        LL odd=0;
        for(LL i=0;i<divisor.size();i++)
        {
            if(mark&(1<<i))
            {
                odd++;
                mul*=divisor[i];
            }
        }
        LL cnt=m/mul;
        if(odd&1)    ans+=cnt;
        else ans-=cnt;
    }
    return m-ans;
}
LL n,k;
int main()
{
    while(scanf("%lld%lld",&n,&k)!=EOF)
    {
        LL left=0;
        LL right=1LL<<60;
        while(right-left>1)
        {
            LL mid=(left+right)>>1;
            LL cnt=sieve(n,mid);
            if(cnt>=k)
            {
                right=mid;
            }
            else
            {
                left=mid;
            }
        }
        printf("%lld
",right);
    }
    return 0;
}

 Java版：

import java.util.Scanner;
import java.util.ArrayList;
public class Main{ 
    Scanner in = new Scanner(System.in);
    long m, k;
    long sieve(long n, long m)
    {
        ArrayList<Long> divisor = new ArrayList();
        for(long i = 2; i * i <= n; i++)
        {
            if(n % i == 0)
            {
                divisor.add(i);
                while(n % i == 0) n /= i;
            }
        }
        if(n > 1) divisor.add(n);
        long ret = 0;
        for(long mark = 1, size = divisor.size(); mark < (1 << size); mark++)
        {
            long odd = 0;
            long mul = 1;
            for(int i = 0; i < size; i++)
            {
                if((mark & (1L << i)) != 0)
                {
                    odd++;
                    mul *= divisor.get(i);
                }
            }
            if(odd % 2 == 1)
            {
                ret += m / mul;
            }
            else
            {
                ret -= m / mul;
            }
        }
        return m - ret;
    }
    Main()
    {
        while(in.hasNext())
        {
            m = in.nextLong();
            k = in.nextLong();
            long left = 0, right = 1L << 62;
            while(right > left)
            {
                long mid = (right + left) >> 1;
                long s = sieve(m, mid);
                if(s >= k)
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
            System.out.println(right);
        }
    }
    public static void main(String[] args){
        
        new Main();
    }
}