はまやんはまやんはまやん

hamayanhamayan's blog

Find Remainder [CSAcademy #63 C]

https://csacademy.com/contest/round-63/task/find-remainder/

N要素の配列A,Bがある。
この時B[i] = A[i] % Kとなるような最小の自然数Kを求めよ。
もし、存在しないならば-1と答えよ。
※ 問題文では「B[i] = A[i] mod K」とあるが合同式ではないので注意

解法

コーナーケースがむちゃくちゃあるので大変。
 
まず、自明でダメな場合を取り除こう。
余りを取って数が大きくなるということは無いので、A[i]<B[i]の要素が1つでもあればダメ。
これ以降はA[i]≧B[i]と考えられる。
 
さて、考察として「13 % K = 5」を考えてみよう。
13と5の差を見てみると8であるため、このように書き換えることができる
「13 = 8 + 5」
これを見てみると剰余によって8が消えればいいので、Kの候補は8の約数ということになる。
その為、全ての数の差を取ってきて、全ての数の約数になるような数がKの候補となる。
これは丁度gcdを取る操作に当たるので、全ての数の差のgcdを取ってくれば、それがKの候補となる。
「13 = 8 + 5」の例ではKの候補は1,2,4,8であるが、1~4で割ると余りが5にはならないので、Kが別途、余りよりも大きいという制約がつく。
そのため、gcdの約数がKの答えとなりうるが、全ての余りよりも必ず大きい必要がある。
よって、普通の答えは差のgcdの約数のうち、全ての余りの最大値よりも大きい数のうち最小の数が答えになる。
もしgcd=1であれば、答えは作れないため「-1」
 
A[i] == B[i]の場合は差が0でgcdには影響を及ぼさないが、A[i] % K = B[i]となるためには、KはA[i]よりも大きい数であればいい。
そのため、差が0の要素がある場合はそのような要素の数の最大値よりもKは大きいという制約がまた、別途つく。
 
あと、全ての要素が同じ場合も処理を分けないとバグる。
あと、答えが出た後にその答えで本当に「A[i]%K=B[i]」となるかをチェックしないと落ちる。
 
他にもコーナーケースを見逃していそうだが、これだけやるとACがもらえる

#define INF INT_MAX/2
int N, A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
int solve() {
    rep(i, 0, N) if (A[i] < B[i]) return -1;
    rep(i, 0, N) C[i] = A[i] - B[i];

    int g = 0;
    int ma = -1;
    rep(i, 0, N) {
        if (C[i] == 0) ma = max(ma, A[i]);
        else g = gcd(g, C[i]);
    }

    if (g == 1) return -1;
    if (g == 0) return ma + 1;

    if (g <= ma) {
        int d = (ma + 1 + g - 1) / g;
        g = d * g;
    }
    
    auto e = enumdiv(g);
    int ma2 = -1;
    rep(i, 0, N) ma2 = max(ma2, B[i]);
    fore(i, e) if (ma2 < i) g = min(g, i);
    rep(i, 0, N) if (A[i] % g != B[i]) return -1;

    return g;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    cout << solve() << endl;
}