A Math Contest P16 - Morbius vs. Suibom

View as PDF

Submit solution

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

Author:
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 \leq N \leq 10^{10}) and K (2 \leq K \leq 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

64

Comments

There are no comments at the moment.