3089974_ac_3390ms_6744k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main
{
    public static void main(String [] args)
    {
        new Main().solve();
    }
    
    private void solve()
    {
        Scanner cin = new Scanner (System.in);
        int fai[] = new int [1000001];
        int m, k, f;
        
        Fai(fai);
        while(cin.hasNext())
        {
            m = cin.nextInt();
            k = cin.nextInt();
            f = fai[m];
            f = (k-1)/f*m;
            k = (k-1)%fai[m]+1;
            int cnt = 0;
            for(int i = f+1; i <= f+m ; i++)
            {
                if(gcd(i,m)==1)
                {
                    cnt++;
                    if(cnt==k)
                    {
                        System.out.println(i);
                        break;
                    }
                }
            }
        }
    }
    
    private void Fai(int fai[])
    {
	int sushu[] = new int [200];
	int i, j, c;
	int comp[] = new int [1000];

	fai[1] = 1;
	sushu[0] = 2;
	c = 0;
	for(i = 2; i < 1000; i++)
	{
		if(comp[i]==0)
		{
			for(j = i * 2; j < 1000; j += i)
			{
				comp[j] = 1;
			}
		}
	}
	for(i = 2; i < 1000; i++)
	{
		if(comp[i]==0)
		{
			sushu[c ++] = i;
		}
	} 
	for(j = 2; j < 1000001; j++)
	{
		for(i = 0; i < c ;i ++)
		{
			int k = j/sushu[i];
			if(j%sushu[i] == 0)
			{
				if(k%sushu[i] == 0)
					fai[j] = fai[k]*sushu[i];
				else
					fai[j] = fai[k]*(sushu[i] - 1);
				break;
			}
		}
		if(i == c)
                {
                    fai[j] = j - 1;
                }
	}

}

    private int gcd(int i, int m) 
    {
        int r = i%m;
        
        while(r!=0)
        {
            i = m;
            m = r;
            r = i%m;
        }
        return m;
    }

}