yukicoder No.990 N×Mマス計算（Kの倍数）

No.990 N×Mマス計算（Kの倍数） - yukicoder

がかのどちらかである時、がの倍数であるようなの組合せは何通りあるかという問題です。

WAを抜け出せなかったので解説に沿って解いたのですが、解いていて楽しかったので記事を書くことにしました。

（全面的にC++における表現を使用しています）

解法

op == '+'の場合

がの倍数となるのは、をで割った余りの和がの倍数である時。

そのため、予めの値ごとにカウントしておくことで、各においての値をカウントしておいた中から探すだけで済むようになる。

注意

• とすると、の時、の値を探してしまう。

• （C++では）とすると、負の値が出力されてしまう。

• カウンターは、であることから、配列ではなくmapを使用する。

コード

    map<int, int> dict;
    for (int i = 0; i < m; i++) {
      int b; cin >> b;
      dict[b % k]++;
    }
    for (int i = 0; i < n; i++) {
      int a; cin >> a;
      ans += dict[(k - a % k) % k];
    }

op == '*'の場合

がの倍数となるのは、との最大公約数の積がの倍数である時。

そのため、予めとの最大公約数の値ごとにカウントしておくことで、各において全てのとの最大公約数の積がの倍数である時、それぞれの個数の積を計算するだけで済む。

注意

• の約数の個数は、二重ループで間に合う範囲内である。

• カウンターはであることから、配列ではなくmapを使用する。

• 最大公約数の積と個数の積は整数オーバーフローする。

コード

    /* typedef pair<int, int> P; */

    map<int, int> dict1;
    map<int, int> dict2;
    for (int i = 0; i < m; i++) {
      int b; cin >> b;
      dict1[gcd(b, k)]++;
    }
    for (int i = 0; i < n; i++) {
      int a; cin >> a;
      dict2[gcd(a, k)]++;
    }
    for (P p1 : dict1) {
      for (P p2 : dict2) {
        if (1LL * p1.first * p2.first % k == 0) {
          ans += 1LL * p1.second * p2.second;
        }
      }
    }

一言

記事を書くのが面倒になっているせいか、説明が適当になってしまっているので、余裕ができるまでしばらく休止した方が良いのかもしれません。