[NOIP1999] 提高组 洛谷P1014 Cantor表
2024-08-30 16:11:05
题目描述
现代数学的著名证明之一是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才算对
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int x,y;
int n;
int sum;
int main(){
int i,j;
cin>>n;
sum=;
for(i=;i<=n;i++){
if(sum+i>=n)break;
sum+=i;
}
x=i;y=;
for(i=sum+;i<n;i++){
x--;
y++;
}
printf("%d/%d\n",x,y);
return ;
}
最新文章
- Hibernate5.2之一对一外键关联(五)
- mysql学习(1)-linux操作系统源码包安装
- 【POJ】2096 Collecting Bugs
- LoadRunner性能测试结果分析
- MySQL显示连接的数据库名
- paip.输入法编程---词频顺序order by py
- BZOJ 3039: 玉蟾宫( 悬线法 )
- 用于编译cm-12.0 的 local_manifest.xml文件
- PHP IOS PUSH Demo
- Fitting Bayesian Linear Mixed Models for continuous and binary data using Stan: A quick tutorial
- ASP.NET上传文件到远程服务器(HttpWebRequest)
- 在JS中调用CS里的方法(PageMethods)
- laravel启动过程简单解析
- 下划线字符串camel
- java-信息安全(八)-迪菲-赫尔曼(DH)密钥交换
- 使用UWA GOT优化Unity性能和内存
- sql server 我常用的语句
- Hive数据类型及文本文件数据编码
- 建站相关-github+hexo, Markdown
- 【python】python彻底卸载的方法【windows安装版卸载的示例】