2013
11-12

# Happy 2006

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

//* @author: [email protected]
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
int a=in.nextInt();
int b=in.nextInt();
if(a==1)System.out.println(b);
else{
ArrayList< Integer> arr=new ArrayList< Integer>();
for(int i=1;i< a;i++)
{
int m=a,n=i;
while(m%n!=0)
{
int w=m;
m=n;
n=w%n;
}
}
int c=arr.size();
int k=b/c;
int u=b%c;
if(u==0){
u=c;
k-=1;
}
System.out.println(a*k+arr.get(u-1));
}
}
}
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。