題目敘述：
給x1, x2, P, K，求：
P1*x1 - N1*x1 + P2*x2 - N2*x2 = P
P1 + N1 + P2 + N2 = K
的可行解 P1, N1, P2, N2 其中一組。
x1, x2 <= 40000，P <= 40000，K <= 2000000000
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
很明顯的，這是一題特別的擴展歐幾里德題目
但需要一些很麻煩的運算及分析
最起先，要求得 P1-N1 跟 P2-N2 分別的可行解（分別設成A, B）
先求ax+by = gcd(a, b)的 x 和 y （或稱A或B）
可以知道兩個解都會分別小於 x2 和 x1
{
pf: 用數學歸納法，而且用我所使用的ext_gcd較好證明
}
為了方便起見，可以將 P1, N1 調成 (t+abs(A), t) 或 (t, t+abs(A))，端看A的正負
而 P2, N2 調成 (abs(B), 0) 或 (0, abs(B))，端看B的正負
這麼調整的話，即可知道只要符合 2*t >= 0 時，便是一個這題的解，無需任何其他限制
而 t 即是 (K-abs(A)-abs(B)) / 2，所以我們想做的便是將abs(A)+abs(B)最小化且是偶數
有很多種作法可以讓abs(A)+abs(B)最小化（A跟B是變量可以不斷的分別+x2/gcd, -x1/gcd）
可以知道『abs(A)+abs(B)』對『改變量』呈現一個谷狀
{
說明: 假設一開始兩個在零的異側，很明顯會呈現谷狀。若在同側，則要端看何者間隔大，將他不斷往零的方向移動，最後如果穿越零了，變成互相位於異側，則只會上升
}
所以可以直接用暴力去求得，剩下的就是調整奇偶即印出而已
但你可能覺得這樣跑太慢了，事實上重點就在於其與零的位置
因為 A <= x2*P/gcd 且 B <= x1*P/gcd，而間隔為x2/gcd和x1/gcd，所以最多改變約P次，for只會循環 P 次，時間複雜度O(P)，是OK的
//By momo
#include<cstdio>
#include<algorithm>
using namespace std;
int ext_gcd(int a, int b, int& x, int& y){
int v = a;
if(b == 0){ x = 1, y = 0; }
else{
v = ext_gcd(b, a%b, y, x);
y -= (a / b) * x;
}
return v;
}
int main()
{
int x1, x2, p, k, d1, d2, A, B;
scanf("%d%d%d%d", &x1, &x2, &p, &k);
int gcd = ext_gcd(x1, x2, A, B);
if(abs(p) % gcd) return puts("NO"), 0;
A *= p/gcd, B *= p/gcd; d1 = x2/gcd; d2 = x1/gcd;
for( ; abs(A-d1) + abs(B+d2) < abs(A) + abs(B); A -= d1, B += d2);
for( ; abs(A+d1) + abs(B-d2) < abs(A) + abs(B); A += d1, B -= d2);
if(abs(A) + abs(B) > k) return puts("NO"), 0;
if((k-abs(A)-abs(B)) % 2){
if((d1+d2) % 2 == 0) return puts("NO"), 0;
if(abs(A-d1)+abs(B+d2) < abs(A+d1)+abs(B-d2)) A -= d1, B += d2;
else A += d1, B -= d2;
if(abs(A)+abs(B) > k) return puts("NO"), 0;，
}
int t = (k-abs(A)-abs(B)) / 2;
int p1, n1, p2, n2;
if(A < 0) p1 = t, n1 = t-A;
else p1 = t+A, n1 = t;
if(B < 0) p2 = 0, n2 = -B;
else p2 = B, n2 = 0;
printf("YES\n%d %d %d %d\n", p1, n1, p2, n2);
}
