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);
    }

}