Let's "Clone" It

この問題では主に数学的思考を問います。

問題の条件からsantarate君からもnumDeer君からもプレゼントの個数を変更することが可能なため、単に $K$ を選んで操作をすればよいです。
まず $1$ 種類のときを考えてみます。この場合いかなる個数であっても $1$ 回の操作で可能です。すなわち $K=|A_1-B_1|$ として選ぶことで必ず等しくできます。
$2$ 種類のとき、例えば $A=(8,5),B=(2,9)$ の場合は $K=2$ を選び、$B_1$ に $2$ を $3$ 回だけ足し、$A_2$ に $2$ 回だけ足すことで等しくできます。また $K=1$ でも達成させることも可能ですが、その場合は合計で $8$ 回の操作のため最小値とはなりません。 また $K=1,2$ 以外ではどんな操作をしようと絶対に $A,B$ がともに等しくなることはありません。これは各個数を $K$ で割ったあまりを考えることで示すことができます。
ここで $A,B$ がともに等しくなる $K$ を考えると、$A_1,B_1$ と $A_2,B_2$ に $K$ を $n$ 回足すと等しくなるもの、すなわち $|A_1-B_1|,|A_2-B_2|$ の正の公約数を $K$ に選べばよいです。その中で操作回数を最小化するためには $K$ を最大にすることが必要十分なので、$K$ は最大公約数を選ぶことが適切です。

以上から $N$ 種類のとき、$K$ は $|A_1-B_1|,|A_2-B_2|,...|A_N-B_N|$ の最大公約数を選べばよいことがわかります。そしてそれぞれの個数に足すべき回数はちょうど $|A_i-B_i|$ を $K$ で割った商 $q_i$ に等しい (最大公約数の性質よりあまりは $0$ であるから、必ず整数になるため) ので、求める答えは $q_1+q_2+...+q_N$ となります。
実装方法によりますが、一般に $X,Y$ の最大公約数を求めるアルゴリズム※は $O(\log_{}X)$ で実装できるので、全体で $O(N+\log_{}\max(|A_i-B_i|))$ で、この問題を解くことができます。ただし $|A_i-B_i|=0$ となる $i$ が $c$ 個あるとき、$K$ はそれらを除いた $(N-c)$ 個の数値の最大公約数を選ばなくてはならないことに注意してください。
解答例(C++)は以下のようになります。

xxxxxxxxxx

#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)

#define srep(i,a,b) for(int i = a; i <= b; i++) //[a,b]

#define all(A) (A).begin(),(A).end()

#define rall(A) (A).rbegin(),(A).rend()

#define pmt(A) next_permutation(all(A))

using namespace std;

using ll = long long;

using ull = unsigned long long;

using P = pair<ll,ll>;

using pq = priority_queue<ll,vector<ll>,greater<ll>>;

const ll inf = 8e18;

const int iinf = (int)1e9;

const int mod9 = 998244353;

const int mod1 = 1000000007;

struct Edge { int to; ll cost; int from; };

bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }

using Graph = vector<vector<int>>;

using SGraph = vector<set<ll>>;

template <typename T>

ll siz(T& a){return (ll)a.size();}

​

long long gcd(long long x,long long y){

    if(x*y == 0) return (x == 0 ? y : (y == 0 ? x : 0));

    if(x < y) swap(x,y);

    return (x%y == 0 ? y : gcd(y,x%y));

}

​

int main(void){

    int n; cin >> n;

    vector<int> A(n),B(n);

    rep(i,n) cin >> A[i];

    rep(i,n) cin >> B[i];

​

    int g = 0;

    rep(i,n){

        if(A[i] != B[i]){

            if(g == 0) g = abs(A[i]-B[i]);

            else g = gcd(abs(A[i]-B[i]),g);

        }

    }

​

    ll ans = 0;

    if(g != 0) rep(i,n) ans += abs(A[i]-B[i])/g;

    cout << ans;

}

※このアルゴリズムはユークリッドの互除法と呼ばれるものです。詳細はここでは省略しますが、ぜひ調べてみるといいと思われます。

追記 (03/04. 19:57)

解答例を修正しました。前の解答例ではafter_contest-01,02でREとなります。