Cantor表 1999年NOip全國聯賽普及組 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver 題解 題目描述 Description 現代數學的著名證明之一是Georg Cantor證明了有理數是可枚舉的。他是用下面這一張表來證明這一命題的： 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 … … 我們以Z字形給上表的每一項編號。第一項是1/1，然后是1/2，2/1，3/1，2/2，…
輸入描述 Input Description 整數N（1≤N≤10000000）
輸出描述 Output Description 表中的第N項
樣例輸入 Sample Input 7
樣例輸出 Sample Output 1/4
數據范圍及提示 Data Size & Hint 見描述
思路： 測試數據1個億，O(N)是不行的了，所以要換個方法。我們可以清晰的看到，格局是一個斜三角，并且頂部往下是1,2,3,4個數字，同時可以看到一個規律，就是奇數斜行是向上，偶數向下，根據這個規律可以直接算出位于第幾行
CODES:
#include<stdio.h>#include<string.h>int main(){ int n,sum = 0; scanf("%d",&n); int i=1; for(;;){ if(sum+i>=n){ break; }else{ sum+=i; i++; } } if(i&1){ //上 int t = n-i*(i-1)/2;新聞熱點
疑難解答
