Happy 2006

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

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.

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).

Output the K-th element in a single line.

2006 1

2006 2

2006 3

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=;

int m,k;

int relative[MAXN],top;

int gcd(int a,int b)

{

    if(b==)    return a;

    else return gcd(b,a%b);

}

void sieve()

{

    for(int i=;i<=m;i++)

    {

        if(gcd(i,m)==)

        {

            relative[top++]=i;

        }

    }

}

int main()

{

    while(scanf("%d%d",&m,&k)!=EOF)

    {

        top=;

        sieve();

        int n=(k-)/top;

        int z=(k-)%top;

        int res=n*m+relative[z];

        printf("%d\n",res);

    }

    return ;

}

#include <cstdio>

#include <vector>

using namespace std;

typedef long long LL;

LL sieve(LL n,LL m)

{

    vector<LL> divisor;

    for(LL i=;i*i<=n;i++)

    {

        if(n%i==)

        {

            divisor.push_back(i);

            while(n%i==)    n/=i;

        }

    }

    if(n>)    divisor.push_back(n);

    LL ans=;

    for(LL mark=;mark<(<<divisor.size());mark++)

    {

        LL mul=;

        LL odd=;

        for(LL i=;i<divisor.size();i++)

        {

            if(mark&(<<i))

            {

                odd++;

                mul*=divisor[i];

            }

        }

        LL cnt=m/mul;

        if(odd&)    ans+=cnt;

        else ans-=cnt;

    }

    return m-ans;

}

LL n,k;

int main()

{

    while(scanf("%lld%lld",&n,&k)!=EOF)

    {

        LL left=;

        LL right=1LL<<;

        while(right-left>)

        {

            LL mid=(left+right)>>;

            LL cnt=sieve(n,mid);

            if(cnt>=k)

            {

                right=mid;

            }

            else

            {

                left=mid;

            }

        }

        printf("%lld\n",right);

    }

    return ;

}

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 = ; i * i <= n; i++)

        {

            if(n % i == )

            {

                divisor.add(i);

                while(n % i == ) n /= i;

            }

        }

        if(n > ) divisor.add(n);

        long ret = ;

        for(long mark = , size = divisor.size(); mark < ( << size); mark++)

        {

            long odd = ;

            long mul = ;

            for(int i = ; i < size; i++)

            {

                if((mark & (1L << i)) != )

                {

                    odd++;

                    mul *= divisor.get(i);

                }

            }

            if(odd %  == )

            {

                ret += m / mul;

            }

            else

            {

                ret -= m / mul;

            }

        }

        return m - ret;

    }

    Main()

    {

        while(in.hasNext())

        {

            m = in.nextLong();

            k = in.nextLong();

            long left = , right = 1L << ;

            while(right > left)

            {

                long mid = (right + left) >> ;

                long s = sieve(m, mid);

                if(s >= k)

                {

                    right = mid;

                }

                else

                {

                    left = mid + ;

                }

            }

            System.out.println(right);

        }

    }

    public static void main(String[] args){

        new Main();

    }

}