2021 年百度之星·程式設計大賽 - 初賽一（1004/萌新）

補題連結跳轉

a mod c = b mod c

c >= 2

⇒

c * t1 + k = a（1）

c * t2 + k = b（2）

(1) - (2) ⇒ c(t1 - t2) = (a - b) （此時t可能< 0），為了保證式子兩邊大于0，

是以取絕對值：| c(t1-t2) | = | a - b |

ct = abs(a - b); 此時的t > 0

可以看出右邊是一個常數，設為d ⇒ ct = d，是以當t = 1時，c最大，此時c = d;

如果要使c最小，并且大于等于2，而t是一個正整數，是以C肯定為d大于1的最小的因數。

最後對a，b相等的情況特判下 ⇒ 結果為（c1=2，c2=a=b），再對a = b = 1的情況特判即可（c1 = -1，c2 = -1）

#include <iostream>

using namespace std;

int fn(int x){

    for (int i = 2; i * i <= x; ++i) {
        if(x % i == 0){
            return i;
        }
    }

    return x;
}

int main(){

    int t, a, b;

    cin >> t;

    while (t--){
        cin >> a >> b;
        int m2 = abs(b - a);

        if(a==1 && b==1){
            printf("-1 -1\n");
            continue;
        }else if(m2 == 0){
            printf("%d %d\n", 2, a);
            continue;
        }else if(m2 < 2){
            printf("-1 -1\n");
            continue;
        }

        int m1 = fn(m2);
        printf("%d %d\n", m1, m2);
    }

}