10673 - Play with Floor and Ceiling

 //10673 - Play with Floor and Ceiling

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<conio.h>
using namespace std;

int d,p,q;
void extEuclid(int,int);

int main()
{
    int x,k,t,a;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&x,&k);

        a=x%k;
        if(!a)
            printf("0 %d\n",k);
        else
        {
            a=x/k;
            extEuclid(a,a+1);
            printf("%d %d\n",p*x,q*x);
        }
    }
    return 0;
}

void extEuclid(int a,int b)
{
    int x1;

    if(b==0)
    {
        d=a;
        p=1;
        q=0;
        return;
    }
    extEuclid(b,a%b);

    x1 = p-(a/b) * q;
    p = q;
    q = x1;
}