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