/最低能的暴力枚举,过10/11;
思路就是枚举分子j从0-i,分母从1-n;
把所有的结果都加入string数组的同时前面加上j/i然后加上一堆空
格控制精度,然后数组排序,这样的话j/i小的就在前面.
排完序就是去重,直接取string的0-9位,如果相同就把除了第一个之外的状态全变成true,最后遍历一下子,如果是false就判定是否能化/简最后一化简输出就完事.因为套了俩暴力,时间复杂度应该是平方级别的,应该是数据弱了点,但是在比赛中拿一半分数应该没问题/
import java.util.;
import java.io.;
public class Main{
static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
public static int gcd(int a,int b) {
if(b==0) {
return a;
}else {
return gcd(b,a%b);
}
}
public static void main(String[]args) throws Exception{
int n=Integer.parseInt(bf.readLine());
String str[]=new String[1000010];
int idx=0;
for(int i=1;i<=n;i++) {
for(int j=0;j<=i;j++) {
double c=1.0*j/i;
String sr=Double.toString(c);
str[idx++]=sr+" "+Integer.toString(j)+"/"+Integer.toString(i);
}
}
Arrays.sort(str,0,idx);
boolean st[]=new boolean[idx];
for(int i=0;i<idx;i++) {
for(int j=i+1;j<idx;j++) {
if(str[i].substring(0,10).equals(str[j].substring(0,10))) {
st[j]=true;
}
}
}
for(int i=0;i<idx;i++) {
String s[]=str[i].split(" ");
if(!st[i]) {
String se[]=s[1].split("/");
int a=Integer.parseInt(se[0]);
int b=Integer.parseInt(se[1]);
if(a%gcd(a,b)==0||b%gcd(a,b)==0) {
int t=gcd(a,b);
a/=t;
b/=t;
}
System.out.println(a+"/"+b);
}
}
}
}