SGU 141 Jumping Joe

題目敘述：

給x1, x2, P, K，求：

P₁*x₁ - N₁*x₁ + P₂*x₂ - N₂*x₂ = P 

P₁ + N₁ + P₂ + N₂ = 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);
}