Description
输入一个自然数N
请写一个程序来增序输出分母小于等于N的最简真分数
Input
单独的一行 一个自然数N(1..160)
Output
每个分数单独占一行
最后一行有回车
Sample Input
5
Sample Output
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
Source
cwj
题解：
把所有的分数枚举出来，排序，去重，输出······
代码：
varn,i,j,l:longint;z,m:array[1..10000] of longint;a:array[1..10000] of real;
function gcd(a,b:longint):longint;
varr:longint;
beginwhile b<>0 dobeginr:=a mod b;a:=b;b:=r;end;exit(a);
end;
procedure qsort(l,r:longint);
vari,j,c:longint;k,t:real;
beginif l>=r then exit;i:=l;j:=r;k:=a[l+random(r-l+1)];repeatwhile (a[i]<k) do inc(i);while (a[j]>k) do dec(j);if i<=j thenbegint:=a[i];a[i]:=a[j];a[j]:=t;c:=z[i];z[i]:=z[j];z[j]:=c;c:=m[i];m[i]:=m[j];m[j]:=c;inc(i);dec(j);end;until i>j;qsort(l,j);qsort(i,r);
end;
beginreadln(n);l:=1;m[1]:=1;for i:=1 to n dofor j:=i to n doif gcd(i,j)=1 thenbegininc(l);z[l]:=i;m[l]:=j;end;randomize;for i:=1 to l doa[i]:=z[i]/m[i];qsort(1,l); for i:=1 to l dowriteln(z[i],'/',m[i]);
end.