2013
11-10

# Count on Canton

One of the famous proofs of modern mathematics is Georg Cantor’s demonstration that the set of rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers as shown in the diagram below.
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1


In the above diagram, the first term is 1/1, the second term is 1/2, the third term is 2/1, the fourth term is 3/1, the fifth term is 2/2, and so on.

The input list contains a single number per line and will be terminated by endof-file.

You are to write a program that will read a list of numbers in the range from 1 to 10^7 and will print for each number the corresponding term in Cantor’s enumeration as given below.

3
14
7

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4

import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

while(cin.hasNext())
{
int num = cin.nextInt();
int index = 1;
int result = 0;
while(result <= num)
{
result += index;
index ++;
}
result -= (index-1);

int layer = index - 1;
int offset = num - result;
int up, down = 0;

if(layer % 2 == 0)
{
if(offset == 0)
{
up = 1;
down = layer - 1;
}
else
{
up = offset;
down = layer + 1 - offset;
}
}
else
{
if(offset == 0)
{
up = layer - 1;
down = 1;
}
else
{
up = layer + 1 - offset;
down = offset;
}
}
System.out.println("TERM " + num + " IS " + up + "/" + down);
}
}
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮