#BZOJ4833. 最小公倍佩尔数

最小公倍佩尔数

题目描述

 令(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的值。

输入格式

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

输出格式

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

5 1 233 2 233 3 233 4 233 5 233
1 5 35 42 121