题目链接

https://cn.vjudge.net/contest/307680#problem/A

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

1
2 3

Sample Output

2

题意：

定义He[N]为 在[0,N−1]范围内有多少个数满足式子x^2≡x (mod N)

求HeHe[N]=He[1]×……×He[N]

 

积性函数定义：

对于正整数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的质数的数目
     

结论：

1) 函数He[]是积性函数,对于p，q两个数互质有：He[pq]=He[p]×He[q]

2) 如果p是素数那么He[p]=2且He[p^k]=2

证明：见大佬博客https://blog.csdn.net/codeswarrior/article/details/81433946

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+5;
bool p[N];
int prime[N],cnt=0;
void init(){
	p[0]=p[1]=true;
	for(int i=2;i<N;i++){
		if(!p[i]) prime[cnt++]=i;
		for(int j=0;j<cnt&&(ll)i*prime[j]<N;j++){
			p[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}
ll ksm(ll a,ll b,ll mod){
	ll s=1;
	while(b){
		if(b&1){
			a%=mod;
			s%=mod;
			s*=a;
		}
		a%=mod;
		a*=a;
		b>>=1;
	}
	return s%mod;
}
int main(){
	init();
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m;
		scanf("%d%d",&n,&m);
        ll ans=0;
		for(int i=0;i<cnt&&prime[i]<=n;i++){
			ans+=n/prime[i];
		}
		ans=ksm(2,ans,m);
		printf("%lld\n",ans);
	}	
	return 0;
}