Mike and congruence relation

4.4

30 votes
Modular arithmetic, ad-hoc, Number Theory, Easy, Mathematics, Brute-force search, 簡単
Problem

Mike wrote the remainder of each number from 1 to n when divided by k. He wants to find how many pairs have equal value, namely how many ordered pairs (x,y) (1x<yn) exist such that xy(modk).

Input

The first line contains 2 numbers n,k (1n,k109) separated by space.

Output

Output the number of ordered pairs that satisfy the relation.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The pairs are : (2,4),(1,3),(1,5),(3,5).

Editor Image

?