Cod sursa(job #2349076)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 20 februarie 2019 10:03:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include<cstdio>
const int M=2000000;
int t,a,b,c,x,y,d,i=-1,k;
char p[M];
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;
}
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;
}
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);
}