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

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

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