C - Triangular Relationship

Contest Duration: 2018-09-01(Sat) 12:00 - 2018-09-01(Sat) 13:40 (local time) (100 minutes) Back to Home

C - Triangular Relationship Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

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

制約

$1 \leq N,K \leq 2\times 10^5$
$N,K$ は整数である

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $K$

出力

$N$ 以下の正の整数の組 $(a,b,c)$ であって、 $a+b,b+c,c+a$ がすべて $K$ の倍数であるようなものの個数を出力せよ。

入力例 1Copy

Copy

3 2

出力例 1Copy

Copy

$(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1),(3,3,3)$ が条件を満たします。

入力例 2Copy

Copy

5 3

出力例 2Copy

Copy

入力例 3Copy

Copy

31415 9265

出力例 3Copy

Copy

入力例 4Copy

Copy

35897 932

出力例 4Copy

Copy

Score : $300$ points

Problem Statement

You are given integers $N$ and $K$ . Find the number of triples $(a,b,c)$ of positive integers not greater than $N$ such that $a+b,b+c$ and $c+a$ are all multiples of $K$ . The order of $a,b,c$ does matter, and some of them can be the same.

Constraints

$1 \leq N,K \leq 2\times 10^5$
$N$ and $K$ are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$

Output

Print the number of triples $(a,b,c)$ of positive integers not greater than $N$ such that $a+b,b+c$ and $c+a$ are all multiples of $K$ .

Sample Input 1Copy

Copy

3 2

Sample Output 1Copy

Copy

$(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1)$ and $(3,3,3)$ satisfy the condition.

Sample Input 2Copy

Copy

5 3

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

31415 9265

Sample Output 3Copy

Copy

Sample Input 4Copy

Copy

35897 932

Sample Output 4Copy

Copy