问题 E: Cantor表

时间限制: 1 Sec  内存限制: 125 MB
提交: 18  解决: 10
[状态] [提交] [命题人:外部导入]

题目描述

现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，…

输入

每个测试文件只包含一组测试数据，每组输入一个正整数N（1≤N≤10000000）。

输出

对于每组输入数据，输出表中的第N项。

样例输入 

7

样例输出

1/4

 

 没啥说的，就是个看规律的题，注意是偶数还是奇数行，可能能优化吧

#include<bits/stdc++.h>
using namespace std;
int main(){
	int num;
	cin>>num;
	if(num==1){
		cout<<"1/1";return 0;
	} 
	int i=1;
	for(;;++i){
		if( (i+1)*i/2>num )
			break;
	}
	int f = num - (i-1)*i/2;//第几个
	if(f!=0){
		if(i%2==1){
			cout<<(i+1)-f<<"/"<<f;
		}else{
			cout<<f<<"/"<<(i+1)-f;
		}
	}else{
		if(i%2==1){
			cout<<i-1<<"/"<<1;
		}else{
			cout<<1<<"/"<<i-1;
		}
	}
	
}