問題

ABC108のCの解説がモロ載っているのでまだ解いていない方は注意してください。

問題文

整数 N,K が与えられます。N 以下の正の整数の組 (a,b,c) であって、a+b,b+c,c+a がすべて K の倍数であるようなものの個数を求めてください。ただし、a,b,c の順番を入れ替えただけの組も異なるものとして数えます。また、a,b,c の中に同じものがあっても構いません。

制約

1≤N,K≤2×105

N,K

は整数である

解説を読んでも理解するまで時間がかかったので、どうやって解けばいいのかを書いていきます。分からない方への解説となれればうれしいです。

そもそもの解説文

C: Triangular Relationship

Kが奇数の時、a; b; cをKで割ったあまりはすべて0である必要があります。Kが偶数の時、a; b; cをKで割ったあまりはすべて0であるか、あるいはすべてK/2である必要があります。このような組の個数は、N以下でKで割って0あまるものの個数とK=2あまるものの個数から求めることができるので、この問題を解くことができました。

なんで？？？？？？？？？？？？？？？？？？？

わからん。「多分整数問題で式変形して簡単に求める方法があるんだろうな」って思って色々変形してわからんかったから解説見たんだけど何もわからん。整数問題に弱すぎる。

以下解法です。

modを使った解法

$a+b,b+c,c+a$ がすべて $K$ の倍数になるってどういう時かを考えると、

$a \equiv 0 \pmod K$ and $b \equiv 0 \pmod K$ and $c \equiv 0 \pmod K$ または、

$a \equiv K/2 \pmod K$ and $b \equiv K/2 \pmod K$ and $c \equiv K/2 \pmod K$

しかありません。

（他の分数形のあまりだと $a+b,b+c,c+a$ のどれかが $K$ の倍数にならない）

よって、Kが奇数だとあまりが0のときのみ（K/2が整数にならないので）、偶数だとあまりが0とK/2のときとなります。

これこの記事書いている途中に気付きました あ～～～～～～、なるほどね、そりゃそうだって感じだ。ずっと、次に示す解法で解こうとしていたので時間がかかりました…。

式変形から求める解法

整数問題にありがちな（本当にそうか？）方程式の片側が整数だからもう片側も整数っていうやつを利用します。

$p, q, r \in \mathbb{N}$
$a + b = pK$
$b + c = qK$
$c + a = rK$
とします。

この時

$2a + 2b + 2c = (p + q + r) K$

$2(a + b + c) = (p + q + r)K$

$\displaystyle{\frac{2(a + b + c)}K = p + q + r}$

だから、

$p, q, r \in \mathbb{N}$

より、

$p + q + r$ も整数、よって

$\displaystyle{\frac{2(a + b + c)}K}$

も整数となります。

ここで、 $K$ の偶奇について考えます。

$K$ が奇数の時

$\displaystyle{\frac{2(a + b + c)}K}$

を整数にするためには、 $2$ は偶数なので $a + b + c$ が $K$ の倍数になる必要があります。

ここで、

$b + c = qK$ でしたから、 $a + b + c = a + qK$ となります。これが $K$ の倍数になるためには $a$ が $K$ の倍数になればいいです。よって、 $a$ は $K$ の倍数です。

$b, c$ についても同じように言えるので、 $a, b, c$ は $K$ の倍数となります。

つまり、

a; b; cをKで割ったあまりはすべて0

です。

$K$ が偶数の時

奇数の時と同様に

a; b; cをKで割ったあまりはすべて0

に加えて、

あるいはすべてK/2

が許されます。

これは、 $K$ 偶数より、 $K = 2m; m \in\mathbb{N}$ と置くと、

$\displaystyle{\frac{2(a + b + c)}K = \frac{a + b + c}m}$

となるからです。（ $K$ 奇数の時は分子の $2$ と割れませんでした。）

よって $a + b + c$ は $m$ の倍数となればよく、 $b + c = qK$ より、 $a + b + c = a + qK = a + 2mK$ だから、 $a$ は $m$ の倍数です。

つまり、 $a = ms = Ks/2; s \in \mathbb{N}$ と表せます。ここで $s$ が偶数なら $K$ で割った余りは0、奇数なら割った余りが $K/2$ になります。

同様に、 $b, c$ も求められます。

また、

$p, q, r \in \mathbb{N}$
$a + b = pK$
$b + c = qK$
$c + a = rK$

を考えれば

Kが偶数の時、a; b; cをKで割ったあまりはすべて0であるか、あるいはすべてK/2である必要があります。

です。

これで、Kの偶奇により条件が違うことがわかり、それぞれで条件を満たす個数を数えればよくました。

組み合わせの個数

組み合わせは何を選ぶかなので、 $(条件に合う数字の個数)^ 3$ してやればいいです。

$K$ 偶数の時の数え方に注意しましょう。

提出したコード

以下のようなコードを書けばいいです。

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n, k; cin >> n >> k;
    int cnt = 0, ans;
    for(int i = 1; i <= n; i++){
        if(i % k == 0) cnt++;
    }
    ans = pow(cnt, 3);
    if(k % 2 == 0){// k偶数
        cnt = 0;
        for(int i = 1; i <= n; i++){
            if(i % k == (k / 2)) cnt++;
        }
        ans += pow(cnt, 3);
    }
    cout << ans << endl;
}

まとめ

競プロの整数問題はmodで考えたらわかりやすいことが多い気がします。

というか普通の式変形はしんどい……

modで考えよう！！！！！！！！！！！！！！！！！！！！！！！！！！！

あと、pow使うとたまに手元と、提出先のものとで計算結果が違うことがあるんですが同じような人いますかね…（丸め誤差？）

りつくろいす

英語が苦手です

ABC108のCで詰まった話

問題