首先, 可以知道题目要求解一个 \(ax+by=c\) 的方程, 且 \(x+y\) 最小.
感性证明:
当 \(a>b\) 时,\(y\) 取最小正整数解,\(b\) 减的多,\(a\) 增的少, 此时 \(x+y\) 取最小值.(类似比热容与温度之间)
反之亦然.
- #include<iostream>
- #include<cmath>
- #include<cstdlib>
- using namespace std;
- int a, b, c;
- int exgcd(int a, int b, int &x, int &y) {
- if(b == 0) {
- x = 1, y = 0;
- return a;
- }
- int g = exgcd(b, a % b, x, y);
- int tmp = x;
- x = y;
- y = tmp - (a / b) * y;
- return g;
- }
- void solve(int &x, int &y, int a, int b, int c) {
- int g = exgcd(a, b, x, y);
- x *= (c / g);
- int t = b / g;
- x = (x % t + t) % t;
- y = (a * x - c) / b;
- y = abs(y);
- }
- int main() {
- while(cin>> a>> b>> c) {
- if(!a && !b && !c) break;
- int x1, y1, x2, y2;
- solve(x1, y1, a, b, c);
- solve(x2, y2, b, a, c);
- if(x1 + y1 < x2 + y2) cout << x1 << "" << y1 <<"\n";
- else cout << y2 << "" << x2 <<"\n";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3320155.html