難読。。。でも一見複雑に見えて実はシンプルという問題みたい!!!
問題概要
B の題意、結局求めたい数を V として、
— けんちょん (@drken1215) April 13, 2019
・x を 18 個吐いたら 18 個整数が返って来て、その和を x で割った余りを求めると、それが V % x になっている
・これを 7 回やっていいから V <= 10^6 を当ててね( *˙ω˙*)و
で合ってるかな??
制約
- 使っていい の回数 <= 7
- 当てるべき数 <= 106
考えたこと
題意さえわかれば、中国剰余定理!!!!!
昔、兵士の集まりがあって何人いるかを素早く調べたいとき、
- 3 人組になってもらって何人あまるかを求める (人数を 3 で割ったあまりを求める)
- 5 人組になってもらって何人あまるかを求める (人数を 5 で割ったあまりを求める)
- 7 人組になってもらって何人あまるかを求める (人数を 7 で割ったあまりを求める)
をすることで、中国剰余定理によって、人数を 105 で割ったあまりが一意に求められることを利用した話が有名!
同じように 12, 13, 14, 15, 16, 17, 18 の最小公倍数を L とすると、L >= 106 であり、中国剰余定理によると
- 12 で割ったあまりが a
- 13 で割ったあまりが b
- 14 で割ったあまりが c
- 15 で割ったあまりが d
- 16 で割ったあまりが e
- 17 で割ったあまりが f
- 18 で割ったあまりが g
となる数を L で割ったあまりは存在するならば一意に決まる!ただし、3, 5, 7 の例とは違って、12〜18 は互いに素ではないので、a〜g を決めても答えが存在するとは限らない。
でも今回の問題では、実在の x について、12〜18 で割ったあまりを答えてもらっているので、x を L で割ったあまりは存在して一意に決まる。
中国剰余定理ライブラリは不要
で、一瞬中国剰余定理ライブラリを持っていないと詰まりそうになるのだが、106 程度であればそんなことしなくてよくて、
中国剰余するまでもないのんな。。。
— けんちょん (@drken1215) April 13, 2019
10^6 サイズのバケット用意して、12〜18 で割った余りの該当するところをカウントしてあげて、カウンタ値が 7 になってるものを答えるだけかな??
とすれば OK
#include <iostream> #include <vector> #include <cassert> using namespace std; const int MAX = 1010100; vector<int> mods = {12, 13, 14, 15, 16, 17, 18}; void solve(int N, int M) { vector<int> nums(MAX, 0); for (auto mod : mods) { for (int i = 0; i < 18; ++i) { cout << mod; if (i != 17) cout << " "; } cout << endl; int amari = 0; for (int i = 0; i < 18; ++i) { int a; cin >> a; amari = (amari + a) % mod; } for (int v = amari; v < MAX; v += mod) nums[v]++; } int res = -1; for (int n = 1; n < MAX; ++n) if (nums[n] == 7) res = n; cout << res << endl; int verify; cin >> verify; assert(verify == 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); int T, N, M; cin >> T >> N >> M; for (int _ = 0; _ < T; ++_) { solve(N, M); } }