Cod sursa(job #539656)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 23 februarie 2011 10:44:43
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <cmath>

int v[1024],w[1024];

int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    int n,i,nn,nnn,x,xx,max,j=3,rad,xmax=0;
    scanf("%d",&n); nnn=n-1;
    for(i=1;i<=nnn;++i) v[i]=i;
    nn=n*(n-1)/2;
    if ((nn+n)%n) x=(nn+n)/n+1;
    else x=(nn+n)/n;
    max=x*n-nn;
    xx=x;

    while (!(x%2)) {
        x/=2;
        if (!(max%2)) {max/=2; if(xmax)xmax*=2;else xmax=2;}
        for(i=2;i<=nnn;++i)
            if(!(v[i]%2)) {v[i]/=2; if(w[i])w[i]*=2;else w[i]=2;}
    }
    rad=sqrt(x);
    for(;j<=rad;j+=2)
        while(!(x%j))
        {
            x/=j;
            if (!(max%j)) {max/=j; if(xmax)xmax*=j;else xmax=j;}
            for(i=3;i<=nnn;++i)
                if(!(v[i]%j)) {v[i]/=j; if(w[i])w[i]*=j;else w[i]=j;}
        }
    if (x)
    {
        if (!(max%x)) {max/=x; if(xmax)xmax*=x;else xmax=x;}
        for(i=3;i<=nnn;++i)
            if(!(v[i]%x)) {v[i]/=x; if(w[i])w[i]*=x;else w[i]=x;}
    }
    if (xmax) printf("%d %d\n",max,xx/xmax);
    else printf("%d %d\n",max,xx);
    for(i=nnn;i;--i) if(w[i]) printf("%d %d\n",v[i],xx/w[i]);
                        else printf("%d %d\n",v[i],xx);
    return 0;
}