本文共 2246 字，大约阅读时间需要 7 分钟。
积性函数定义：
对于正整数n的一个算术函数 f(n)，若f(1)=1，且当a,b互质时f(ab)=f(a)f(b)，在数论上就称它为积性函数。若对于某积性函数 f(n) ，就算a, b不互质，也有f(ab)=f(a)f(b)，则称它为完全积性的 常见积性函数： φ(n) －欧拉函数，计算与n互质的正整数之数目 μ(n) －莫比乌斯函数，关于非平方数的质因子数目 gcd(n,k) －最大公因子，当k固定的情况 d(n) －n的正因子数目 σ(n) －n的所有正因子之和 σk(n) － 因子函数，n的所有正因子的k次幂之和，当中k可为任何复数。 Idk(n) －幂函数，对于任何复数、实数k，定义为Idk(n) = n^k （完全积性） λ(n) －刘维尔函数，关于能整除n的质因子的数目 γ(n)，定义为γ(n)=(-1)^ω(n)，在此加性函数ω(n)是不同能整除n的质数的数目In the equation X^2≡X(mod N) where x∈[0,N-1], we define He[N] as the number of solutions.
And furthermore, define HeHe[N]=He[1]*……*He[N] Now here is the problem, write a program, output HeHe[N] modulo M for a given pair N, M.Input
First line: an integer t, representing t test cases.
Each test case contains two numbers N (1<=N<=10^7) and M (0<M<=10^9) separated by a space.Output
For each test case, output one line, including one integer: HeHe[N] mod m.
Sample Input
12 3
Sample Output
2
本题目中的hehe就是积性函数
思路：
1) 函数He[]He[]是积性函数,对于p，q两个数互质有：He[pq]=He[p]×He[q]He[pq]=He[p]×He[q]
2) 如果p是素数那么He[p]=2He[p]=2且He[pk]=2证明结论2：
根据题目要求满足的式子 x2≡x (mod p)x2≡x (mod p) 由同余式定义得到 p|x(x−1)p|x(x−1) 因为题目告诉我们x∈[0,p−1]x∈[0,p−1]所以x小于p 所以p既不整除x也不整除x-1 因此只有一种情况那就是x(x−1)=0x(x−1)=0 此时有x=0或x=1x=0或x=1两种解 故He[p]=2He[p]=2; 对于He[pk]=2的证明同理He[300]=He[2^2 * 3 * 5^2 ]=He[2^2] he[3] *He[5^2]= 2 * 2 * 2；
p有x个质因子则He[p]=2^x； 计算He[p] * He[p-1] * He[p-1] * … * He[1]的话这就用到了阶乘分解因子的方法了，我们知道要求N！中某个因子p有多少个，是不断加N/p直到0位置，而我们需要的只是1-N这些数中有多少个含有p因子，所以加一次N/p即可，然后枚举素因子p即可
（这一步没想到，现查的，不懂得还有很多嘞。。）