1
已解决
栾峻岩
初级天翼
初级天翼
代码如下:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
bool huzhi(int x,int y)
{
if (x>y)
return false;
for (int i=2;i<=x;i++)
{
if (x%i==0 && y%i==0)
return false;
}
return true;
}
struct numb
{
int u,d;
}a[160*160];
bool cmp(numb x,numb y)
{
int x1,y1;
x1=x.u*y.d;
y1=x.d*y.u;
return x1<y1;
}
int main()
{
int n;
cin>>n;
int num=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (huzhi(i,j))
{
a[num].u=i;
a[num].d=j;
num++;
}
}
}
sort(a,a+num,cmp);
cout<<"0/1"<<endl;
for (int i=1;i<num;i++)
{
if (a[i].u!=0 && a[i].d!=0)
cout<<a[i].u<<"/"<<a[i].d<<endl;
}
return 0;
}
只得了27分,请求各位大佬求救!谢谢!
题目网址:point here
题目内容:
题目描述
输入一个自然数N,对于一个最简分数a/b(分子和分母互质的分数),满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。
这有一个例子,当N=5时,所有解为:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
给定一个自然数N,1<=n<=160,请编程按分数值递增的顺序输出所有解。
注:①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。
输入输出格式
输入格式:
单独的一行一个自然数N(1..160)
输出格式:
每个分数单独占一行,按照大小次序排列
输入输出样例
输入样例#1:
5
输出样例#1:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
说明
USACO 2.1
翻译来自NOCOW
我会在线等!
@杨喆 @酷町喵~o( =∩ω∩= )o~ @贾敬波 @葛新 @陆麟瑞 @贾文卓 @樊澄宇 @贾子昂 @刘斐 @梁锦程 @every Dalao