CODE[VS] 天梯 1083 Cantor表

2019-11-11 07:28:12

字體：大中小

供稿：網(wǎng)友

Cantor表 1999年NOip全國聯(lián)賽普及組 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver 題解 題目描述 Description 現(xiàn)代數(shù)學(xué)的著名證明之一是Georg Cantor證明了有理數(shù)是可枚舉的。他是用下面這一張表來證明這一命題的： 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字形給上表的每一項(xiàng)編號。第一項(xiàng)是1/1，然后是1/2，2/1，3/1，2/2，…

這里寫圖片描述 輸入描述 Input Description 整數(shù)N（1≤N≤10000000）

輸出描述 Output Description 表中的第N項(xiàng)

樣例輸入 Sample Input 7

樣例輸出 Sample Output 1/4

數(shù)據(jù)范圍及提示 Data Size & Hint 見描述

思路：測試數(shù)據(jù)1個億，O(N)是不行的了，所以要換個方法。我們可以清晰的看到，格局是一個斜三角，并且頂部往下是1,2,3,4個數(shù)字，同時可以看到一個規(guī)律，就是奇數(shù)斜行是向上，偶數(shù)向下，根據(jù)這個規(guī)律可以直接算出位于第幾行

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;