10673 - Play with Floor and Ceil

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1614

Solution idea : Extended euclid.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

using namespace std;


ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A, ll int B){
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    ll int x,k,a,b,t,g,x1,y1;

    scanf("%lld",&t);

    while(t--)
    {
        scanf("%lld%lld",&x,&k);
        a=floor((double)x/k);
        b=ceil((double)x/k);

        g=ext_gcd(a,b);

        x1=(x*X)/g;
        y1=(x*Y)/g;

        printf("%lld %lld\n",x1,y1);
    }

}