首页 > 搜索 > BFS搜索 > POJ 2773 Happy 2006 [解题报告] Java
2013
11-12

POJ 2773 Happy 2006 [解题报告] Java

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;
	   }
	  if(n==1) arr.add(i);
	  }
	   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树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。