PersonalCorpus 版 (精华区)

1228409 Big Guava ... 10408 Accepted
0:01.324 9600 2002/11/11 02:08:12.472

int gcd(int a, int b)

{
    if (b==0) return a; else return gcd(b,a%b);
}

int cmp(const void *a, const void *b)
{
    int x=(*(int *)a) * (*(((int *)b)+1));
    int y=(*(int *)b) * (*(((int *)a)+1));
    if (x>y) return 1; else if (x==y) return 0; else return -1;
}

int cmp1(const void *a, const void *b)
{
    int x=*(int*)a;
    int y=*(int*)b;
    if (x>y) return 1; else if (x==y) return 0; else return -1;
}
int cmp2(const void *a, const void *b)
{
    int x=*(((int*)a)+2);
    int y=*(((int*)b)+2);
    if (x>y) return 1; else if (x==y) return 0; else return -1;
}

void main()
{
#ifndef ONLINE_JUDGE
    freopen("k:\\iF","r",stdin);
    freopen("k:\\oF","w",stdout);
#endif

    int i,j,k,m,n,c[1001][1011],x,lastm,xi;
    int t[310000][2];
    int req[20000][5];

    for (i=1;i<1001;i++) {
        k=0;
        for (j=1;j<i;j++) if (gcd(i,j)==1) {
            c[i][k]=j;
            k++;
        }
        c[i][k]=0;
    }
    x=0;
    while (scanf("%d%d\n",&req[x][0],&req[x][1])==2) {
        req[x][2]=x;
        x++;
    }
    qsort(req,x,20,cmp1);
    lastm=0;
    for (xi=0;xi<x;xi++) {
        m=req[xi][0]; k=req[xi][1];
        if (lastm!=m) {
            n=0;
            for (i=1;i<=m;i++) for (j=0;c[i][j]>0;j++) {
                t[n][0]=c[i][j]; t[n][1]=i;
                n++;
            }
            qsort(t,n,8,cmp);
            t[n][0]=1; t[n][1]=1;
            lastm=m;
        }
        req[xi][3]=t[k-1][0];
        req[xi][4]=t[k-1][1];
    }
    qsort(req,x,20,cmp2);
    for (i=0;i<x;i++)
        printf("%d/%d\n",req[i][3],req[i][4]);
}