#P4833. [Lydsy1704月赛]最小公倍佩尔数

    ID: 3952 传统题 1000ms 512MiB 尝试: 349 已通过: 170 难度: 9 上传者: 标签>CF2600省选/NOI-莫比乌斯反演最小公倍数线性递推线性筛倍数枚举批量求逆费马小定理快速幂min-max容斥

[Lydsy1704月赛]最小公倍佩尔数

题目描述

令 (1+2)n=e(n)+2f(n)(1+\sqrt 2)^n=e(n)+\sqrt 2f(n),其中 e(n),f(n)e(n),f(n) 都是整数,显然有 (1−2)n=e(n)−2f(n)(1-\sqrt 2)^n=e(n)-\sqrt 2f(n)。令 g(n)g(n) 表示 f(1),f(2),⋯f(n)f(1),f(2),\cdots f(n) 的最小公倍数,给定两个正整数 nn 和 pp,其中 pp 是质数,并且保证 f(1),f(2),⋯f(n)f(1),f(2),\cdots f(n) 在模 pp 意义下均不为 00,请计算 ∑i=1ni×g(i)\sum\limits_{i=1}^ni\times g(i) 其在模 pp 的值。

输入格式

第一行包含一个正整数 TT ,表示有 TT 组数据。

接下来是测试数据。每组测试数据只占一行,包含两个正整数 nn 和 pp 。

输出格式

对于每组测试数据,输出一行一个非负整数,表示这组数据的答案。

样例输入

5
1 233
2 233
3 233
4 233
5 233

样例输出

1
5
35
42
121

数据范围与约定

对于 100%100\% 的数据,1≤T≤2101\le T\le 210,1≤n≤1061\le n\le 10^6,2≤p≤109+72\le p\le 10^9+7,∑n≤3×106\sum n\le 3\times 10^6。

题目来源

鸣谢 Tangjz 提供试题