0
#include<iostream>
using namespace std;
 
long long Gcd(long long a, long long b)
{
    if (b == 0) return a;
    else return Gcd(b, a % b);
}
void exgcd(long long a, long long b, long long& gcd, long long& x, long long& y)
{
    if (!b) {
         gcd = a; x = 1; y = 0;
    }
    else {
        exgcd(b, a % b, gcd, y, x);
        y -= x * (a / b);
    }
}
 
int main()
{
    long long a = 1, b = 0, c = 0, gcd = 0;
    long long x, y, x_general, x_min, y1;
    while (cin >> a >> b >> c) {
        if (a == 0 && b == 0 && c == 0) break;
        gcd = Gcd(a, b);
        if (c % gcd != 0) {
            cout << "No Answer" << endl;
        }
        else
        {
            exgcd(a, b, gcd, x, y);
            long long b1 = b / gcd;
            x_general = (x + b1) * (c / gcd);
            x_min = (x_general % b1 + b1) % b1;
            y1 = (c - a * x_min) / b;
            cout << x_min << " " << y1 << endl;
        }
    }
    return 0;
}

the problem is that a,b,c can be as big as 10^18, even though I use long long int, it still can't apply. the alogrithm should be right, because it can work for a,b,c<=3000.

zengzhilin
  • 1
  • 1
    Your question needs a question. Or a clear problem statement. Are there some specific inputs for which the code does something unexpected? –  Mar 08 '21 at 11:22
  • There are various suggestions for big-integer libraries for C++ at https://stackoverflow.com/questions/124332/c-handling-very-large-integers – k314159 Mar 08 '21 at 11:27

0 Answers0