F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 4833. -- [Lydsy1704月赛]最小公倍佩尔数

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

Time Limit: 8 Sec  Memory Limit: 128 MB
Submit: 322  Solved: 174
[Submit][Status][Discuss]

Description

 令(1+sqrt(2))^n=e(n)+f(n)*sqrt(2),其中e(n),f(n)都是整数,显然有(1-sqrt(2))^n=e(n)-f(n)*sqrt(2)。令g(

n)表示f(1),f(2)…f(n)的最小公倍数,给定两个正整数n和p,其中p是质数,并且保证f(1),f(2)…f(n)在模p意义
下均不为0,请计算sigma(i*g(i)),1<=i<=n.其在模p的值。

Input

第一行包含一个正整数 T ,表示有 T 组数据,满足 T≤210 。接下来是测试数据。每组测试数据只占一行,包含
两个正整数 n 和 p ,满足 1≤n≤10^6,2≤p≤10^9+7 。保证所有测试数据的 n 之和不超过 3×10^6  。

Output

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

Sample Input

5
1 233
2 233
3 233
4 233
5 233

Sample Output

1
5
35
42
121

HINT

Source

鸣谢Tangjz提供试题

[Submit][Status][Discuss]

HOME Back