Pagini recente » Cod sursa (job #863866) | Cod sursa (job #255972) | Cod sursa (job #3205622) | Cod sursa (job #2407481) | Cod sursa (job #2765938)
#include <bits/stdc++.h>
void nos()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
}
namespace BasicMath{
//Euler fuction in O(sqrt(n))
int phi(int n)
{
if(n == 1)
return 0;
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
//Divisors
std::vector < std::pair < int ,int > > Divisors(int n)
{
//{baza, exponent}
std::vector < std::pair< int , int> > ans;
if(n % 2 == 0)
{
int exp = 0;
while(n % 2 == 0)
{
n /= 2;
++exp;
}
ans.push_back({2,exp});
}
int d = 3;
while(n!=1)
{
if(n % d == 0)
{
int exp = 0;
while(n % d == 0)
{
n /= d;
exp++;
}
ans.push_back({d,exp});
}
if(d * d > n)
break;
d+=2;
}
if(n != 1)
ans.push_back({n,1});
return ans;
}
int fastpowsimple(int base,int exp,int MOD)
{
int ans = 1;
while(exp)
{
if(exp & 1)
ans*=base,ans%=MOD;
base *= base;
base %= MOD;
exp >>= 1;
}
return ans;
}
int gcd(int a,int b)
{
while(b)
{
a %= b;
std::swap(a,b);
}
return a;
}
int ExtendedEuclid(int a, int b, int &x, int &y)
{
//a*x + b*y = (gcd(a,b))
if(a == 0)
{
x = 0; y = 1;
return b;
}
int x1,y1;
int d = ExtendedEuclid(b%a,a,x1,y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
}
std::ifstream f("euclid3.in");
std::ofstream g("euclid3.out");
int32_t main()
{
nos();
int teste;
f>>teste;
while(teste --)
{
int a,b,c;
f>>a>>b>>c;
int x,y;
int d = BasicMath::ExtendedEuclid(a,b,x,y);
//std::cout<<d<<"asta e d\n";
if(c%d != 0)
g<<"0 0\n";
else
g<<x * (c/d)<<' '<<y*(c/d)<<'\n';
}
}