ABC 108 C問題 - acchan’s blog

問題概要

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

制約

1 ≤ $N, K$ ≤ 2 $ \times $ 10⁵
$N, K$は整数である。

考えたこと

$a+b$は$K$の倍数

$b+c$は$K$の倍数

$c+a$は$K$の倍数

この３つの条件から、 $2a, 2b, 2c$ は全てKの倍数であることが導かれる。

$K$ が奇数の時

2と$K$は互いに素なので、$a, b, c$が全て$K$の倍数になれば良い。

$K$ が偶数の時

$K$が奇数の時と同じように、$a, b, c$が全て$K$の倍数になる場合の他に、

$$a, b, c \equiv \frac{K}{2} ( mod K ) $$

となる場合を追加する必要がある。

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

int main() {
  ll n, k; cin >> n >> k;
  ll cnt = 0;
  ll ans = 0;
  for(ll i = 1; i <= n; i++) {
    if(i % k == 0) cnt++;
  }
  ans += (ll)(cnt * cnt * cnt);
  if(k % 2 == 0) {
    cnt = 0;
    for(ll i = 1; i <= n; i++) {
      if(i % k == (k/2)) cnt++;
    }
    ans += (ll)(cnt * cnt * cnt);
  }
  cout << ans << endl;

  return 0;
}