Submission #146676

#	Time	Username	Problem	Language	Result	Execution time	Memory
146676		pichulia	분수 (KPI13_fractions)	C++11	1 / 1	82 ms	3064 KiB

fractions

#include<stdio.h>
unsigned long long int find_r(unsigned long long int x, unsigned long long int a, unsigned long long int b)
{
    unsigned long long int l,r,mid;
    l=1; r=b;
    while(l<r)
    {
        mid = (l+r)/2;
        if((x + a*mid)/b < mid) r = mid;
        else l=mid+1;
    }
    return l-1;
}
unsigned long long int gcd(unsigned long long int p, unsigned long long int q)
{
    while(p%q){
        unsigned long long int t=p%q;
        p=q;
        q=t;
    }
    return q;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        unsigned long long int a,b,c,d;
        unsigned long long int k,s;
        scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
        unsigned long long int x,y;
        unsigned long long int p,q,r;
        unsigned long long int g;
        g = gcd(a,b);
        a/=g;
        b/=g;
        g = gcd(c,d);
        c/=g;
        d/=g;
        k = a/b;
        if((c-1)/d > k)
        {
            printf("%llu 1\n",k+1);
        }
        else
        {
            a %= b;
            c %= d;
            if(c==0)c=d;
        y=1;
        while(1)
        {
            p=d+(a*y/b)*d;
            q=c*y;
            if(p<q)break;
            r = a*y%b;
            s = find_r(r,a,b);
           // printf("%llu  %llu %llu %llu   %llu %llu  %llu\n",y, p,q,p-q,r,s, (p+(d-c)*s-q)/c);
            y += s+(p+(d-c)*s-q)/c+1;
        }
        x = a*y/b+1+k*y;
        printf("%llu %llu\n",x,y);
        }
    }
}

Compilation message (stderr)

fractions.cpp: In function 'int main()':
fractions.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&t);
     ~~~~~^~~~~~~~~
fractions.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1