P10663 BZOJ4833 Least Common Multiple of Pell Numbers.

This problem comes from the BZOJ April 2017 monthly contest.

Let $(1+\sqrt{2})^n=e(n)+\sqrt{2}f(n)$, where $e(n), f(n)$ are both integers. It is clear that $(1-\sqrt{2})^n=e(n)-\sqrt{2}f(n)$. Let $g(n)=\operatorname{lcm}(f(1),f(2),\dots,f(n))$. Given two positive integers $n, p$, where $p$ is a prime number, and it is guaranteed that $f(1), f(2), \dots, f(n)$ are all non-zero modulo $p$, compute the value of $\sum \limits_{i=1}^n i\times g(i)$ modulo $p$.

The first line contains a positive integer $T$, meaning there are $T$ test cases. The following lines are the testdata. Each test case occupies one line and contains two positive integers $n$ and $p$.

For each test case, output one line containing one non-negative integer, which is the answer for this test case.

Constraints: for $100\%$ of the testdata, $1\leq T\leq 210$, $1\leq n\leq 10^6$, $2\leq p\leq 10^9+7$, $\sum n\leq 3\times 10^6$. Translated by ChatGPT 5