A Math Contest P16 - Morbius vs. Suibom

View as PDF

Submit solution

Points: 25
Time limit: 2.0s
Memory limit: 512M

Problem type

Let f(x, y) be the lowest common multiple of x and y and g(x, y) be the greatest common divisor of x and y. Determine \sum_{x=1}^N \sum_{y=1}^N f(x, y) \times g(x, y)^2 modulo a prime number, K.

Input Specification

The only line will contain two space-separated integers, N (1 \le N \le 10^{10}) and K (2 \le K \le 2 \times 10^9).

Output Specification

Output \sum_{x=1}^N \sum_{y=1}^N f(x, y) \times g(x, y)^2 modulo K.

Sample Input

10 131

Sample Output



There are no comments at the moment.