Cod sursa(job #2781061)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 8 octombrie 2021 13:23:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstdio>
const int M=2000000;
int t,a,b,c,x,y,d,i=-1,k;
char p[M];
inline int A()
{
  	int s=0,m=1;
  	if(p[i+1]=='-')
  		m=-1,i++;
  	for(i++;p[i]>='0';++i)
  		s=s*10+p[i]-48;
  	return s*m;
}
inline void S(int x,char c)
{
	if(x<0)
        x=-x,p[k++]='-';
    int i,d=x>999999999?10:x>99999999?9:x>9999999?8:x>999999?7:x>99999?6:x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,--i)
        p[k+i]=x%10+48;
    p[k+d]=c,k+=d+1;
}
inline int W(int a,int b,int &x,int &y)
{
    int p,r,q;
    if(!b) {
        x=1,y=0;
        return a;
    }
    q=W(b,a%b,p,r),x=r,y=p-a/b*r;
    return q;
}
int main()
{
    freopen("euclid3.in","r",stdin),freopen("euclid3.out","w",stdout),fread(p,1,M,stdin),t=A();
    while(t--) {
        a=A(),b=A(),c=A(),d=W(a,b,x,y);
        if(c%d)
        	S(0,' '),S(0,'\n');
        else
        	S(x*(c/d),' '),S(y*(c/d),'\n');
	}
	fwrite(p,1,k,stdout);
	return 0;
}