×

计蒜客

  1. 题库
  2. Convex Hull
  3. 问答
  • 18.94%
  • 1500ms
  • 131072K

We define a function $gay(i)$:

$$\displaystyle gay(i)=\left\{ \begin{array}{rcl} & 0, \quad& if \quad i = k*x*x, x > 1, k \geq 1 \\ & i * i ,\quad& else \end{array} \right. $$

Now your task is to calculate$$\displaystyle \sum_{num=1}^n (\sum_{i=1}^{num} gay(i)) \mod p $$

Input

Multiple test cases. Please use EOF.

In each test case, there are two integers $n$, $p$, which are described above.

$1 \leq n \leq 10^{10},1 \leq p \leq 10^{11}$.

The number of test cases is no more than $100$.

Output

For each test case print the answer in one line.

样例输入

1 10
8 19230817

样例输出

1
396

题目来源

ACM-ICPC 2018 沈阳赛区网络预赛

想挑战这道题吗

  • main.c