AtCoder ABC 108 C - Triangular Relationship (ARC 102 C) (緑色, 300 点)

editorial に載っている解法は整数論で でやっているし、僕も本番それでやったけど、この制約なら全探索でパッと書けるべきですね...

参考:

ABC108/ARC102 C: 解説に書かれていませんが、制約が手加減されているので a か a % K の値を全探索できます、この方が解説より競プロ的な解法で、強くなるには解説の通りできないとダメということはないです。https://t.co/Ykp6RofLSZ

— えびま (@evima0) 2018年9月1日

問題へのリンク

問題概要 (ARC 102 C / ABC 108 C)

整数 が与えられる。

, , がすべて の倍数となるような を満たす整数 の組を数え上げよ。

制約

• 

解法 1: a % K の値で全探索

a % K を決め打つと b % K, c % K のとるべき値が一意に決まることを利用します (a+b, a+c が K の倍数であることから)。そうして決まった b, c について b+c が K の倍数になっているかどうかを check します。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k; cin >> n >> k;
    vector<long long> num(k, 0);
    for (int i = 1; i <= n; ++i) num[i%k]++; // num[x] = kで割ってxあまる数が1以上N以下に何個あるか
    long long res = 0;
    for (int a = 0; a < k; ++a) {
        int b = (k-a) % k;
        int c = (k-a) % k;
        if ((b+c) % k != 0) continue;
        res += num[a] * num[b] * num[c];
    }
    cout << res << endl;
}

解法 2: O(1) で解く (本番でやった)

整数論的考察をする上では、以下の性質を心から理解しておくと強い。これは初等整数論の理論を構築する上で非常に重要な足がかりとなる定理です:

---

整数 が与えられる。
整数 が互いに素であるとき、 が で割り切れるならば、 が で割り切れる。

---

合同式で条件を表すと

となる。まず

⇔ (両辺から を引く)

となることが言える。このことは合同式を用いなくても

• が の倍数
• が の倍数
• よって、 も の倍数
• よって、 と を で割ったあまりは等しい

という風に考えてもできる。さて、対称性から、

となることがわかる。ここまでで という条件を反映したが、まだ という条件は考慮していない。なのでこれを考える:

⇔
⇔

となることがわかる。つまり は で割り切れる。ここで、冒頭の定理を思い出すと、 と が互いに素であってほしいという気持ちになる。なので場合分けする。

K が奇数のとき

が奇数なら と は互いに素なので、 は で割り切れることから、 は で割り切れることとなる。つまり、

である。つまり、 はすべて の倍数ということである。答えは、 以下の の倍数の個数を として、 個

K が偶数のとき

とおく。そうすると、

は で割り切れる
⇔ は で割り切れる

という風になることから、

• 
• 
• 

である。さて、ここから一瞬

• 

であると早とちりしそうになるが、それは違う。まず、

⇔ または

であることに注意する (例えば のとき、 は 3 の倍数で、これは を 6 で割ったあまりが 0 か 3 であるということと同じである)。 であることから、

• または

であることが言える。これは とは違う。 としてしまうと、

• 
• 
• 

みたいなケースも含んでしまうが、こういうのは条件を満たしていない。

さて、あとは数え上げる:

• のとき、 以下の の倍数の個数を
• のとき、 以下の で割って あまる整数の個数を

として、答えは 個になる。

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    if (k % 2 == 0) {
        long long a = n / k;
        long long b = (n + (k/2)) / k;
        cout << a*a*a + b*b*b << endl;
    }
    else {
        long long a = n / k;
        cout << a*a*a << endl;
    }
}

さらに

今回の「互いに素」にまつわる整数の整除の定理をつきつめると、以下のことが言える。

---

合同方程式 を解きたい。

• と が互いに素のとき、 と解ける
• そうでないとき、 と の最大公約数を として、 , とする ( と は互いに素になることに注意)
  • が の倍数のとき、 とすると、元の方程式は に帰着
  • が の倍数でないとき、解なし

---