题目描述
现代数学的著名证明之一是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,…
输入输出格式
输入格式:
整数N(1≤N≤10000000)
输出格式:
表中的第N项
输入输出样例
输入样例#1:
7
输出样例#1:
1/4
有各种各样的暴力方法。
观察发现第x行第y列的分数是x/y
第n个斜行的分数数量为n
先找到目标分数所在的斜行,然后挨个往左下方找,每次移动x++ y--
不知道是题目描述里的矩阵有问题,还是洛谷测试数据有问题,输出的时候要输出y/x才算对
1 /*by SilverN*/ 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 int x,y; 9 int n;10 int sum;11 int main(){12 int i,j;13 cin>>n;14 sum=0;15 for(i=1;i<=n;i++){16 if(sum+i>=n)break;17 sum+=i;18 }19 x=i;y=1;20 for(i=sum+1;i