九州大学プログラミングコンテスト2018 I - Buffalo
問題
n個の容器がありi番目の容器にはa[i]リットルの水を入れることができる
これらから2個の容器を選び、以下の操作をそれぞれ任意の回数行い、2個の容器に合計でkリットルの水が入っている状態にしたい
1) 一方の容器を水で満たす
2) 容器xからもう一方の容器yに、yがいっぱいになるかxが空になるまで水を移す
3) 一方の容器の中の水を全て捨てる
これが可能な容器のペアの個数を求めよ
2 <= n <= 3*10^5
1 <= k <= 2*10^6
1 <= a[i] <= 10^6
解法
こういうパズルにおいて最終的に残せる水の量は、2つの容器の容量をx,yとすると、gcd(x,y)の倍数 かつ x+y以下 の任意の正整数であることが証明できる
参考: Puzzle DE Programming / 水差し問題
よって答えは
「gcd(x,y)がkの約数 かつ x+y>=k であるような容器x,yのペアの個数」
となる
で約数とかgcdといえば包除原理
f(i): 容量x,yがどちらもiの倍数かつx+y>=kであるような容器のペアの個数
とする
これはしゃくとり法でO(klogk)で求められる
次に
g(i): gcd(x,y)=iかつx+y>=kであるような容量x,yの容器のペアの個数
とすると、
g(i) = f(i) - Σg(j) (j: iより大きいiの倍数)
で求められ、これもO(klogk)でいける
あとはkの正の約数i全てについてg(i)を足し合わせればそれが答え
実装
e[i]: 容量iの容器の個数
f[]を埋めるとこは
x: 容量がiの倍数であるような容器の容量一覧(昇順)
r: x[j]+x[r]がk未満になるようなrの最大値
を意味する
x[j]とペアにできるのはxのr番目より右側の容器全て
#define int long long int n, k, a[300300], e[1001001], f[2002002], g[2002002], res; vector<int> x; signed main() { cin >> n >> k; rep(i,n) { cin >> a[i]; e[a[i]]++; } reps(i,1,1001001) { x.clear(); for (int j=i; j<1001001; j+=i) rep(l,e[j]) x.push_back(j); int m = x.size(), r = m-1; rep(j,m-1) { while (r>=0 && x[j]+x[r]>=k) r--; f[i] += m - max(j,r) - 1; } } for (int i=1001000; i>=1; i--) { g[i] = f[i]; for (int j=i*2; j<1001001; j+=i) g[i] -= g[j]; if (k%i==0) res += g[i]; } cout << res << endl; }
