UVa 10673 - Play with Floor and Ceil Solution

#include <iostream>
#include <cmath>
int a,b,x,y;
int gcd(int a,int b,int &x,int &y){
    if(a==0){
        x=0,y=1;
        return b;
    }
    int x1,y1;
    int hcf=gcd(b%a,a,x1,y1);
    x=y1-(b/a)*x1;
    y=x1;
    return hcf;
}
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int X,K;
        cin>>X>>K;
        a=X/K,b=(X+K-1)/K;
        int hcf=gcd(a,b,x,y);
        cout<<(X/hcf)*x<<' '<<(X/hcf)*y<<endl;
    }
}