Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)

Total Submission(s): 1463    Accepted Submission(s): 475

Problem Description

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]He[N]在[0,N−1][0,N−1]范围内有多少个数满足式子x2≡x (mod N)x2≡x (mod N)

求HeHe[N]=He[1]×……×He[N]，He[n]是满足方程解的个数

 

由欧拉定理

这里φ(n)=2，即小于等于n的素数都满足φ(n)=2    （φ(n)是小于等于n且与n互质的数的个数）

每一个素数对应两个满足方程的解

 

所有He[n]=满足方程解的个数=2^num（num是小于n的所有质数的个数）

因为题目让求HeHe函数

HeHe函数是He函数的阶乘

故根据我们上面证明的结论

我们要求He[1]，He[2],⋯He[N]He[1]，He[2],⋯He[N]

这就用到了阶乘分解因子的方法了，我们知道要求N！中某个因子p有多少个，是不断加N/p直到0位置，而我们需要的只是1-N这些数中有多少个含有p因子，所以加一次N/p即可，然后枚举素因子p即可

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long longconst int maxn=1e7+5;const int N=7e5+5;bool isprime[maxn];ll prime[N],cnt;void init()//求小于n的所有素数{    cnt = 0;    memset(isprime,true,sizeof(isprime));    for(int i = 2; i < maxn; i++)    {        if(isprime[i])        {            prime[cnt++] = i;            for(int j = i + i; j < maxn; j += i)            {                isprime[j] = false;            }        }    }}ll q_pow(ll a,ll b,ll mod){    ll ans = 1;    while(b)    {        if(b & 1)            ans = ans * a % mod;        b >>= 1;        a = a * a % mod;    }    return ans;}int main(){  init();  ll n,m,t;  scanf("%lld",&t);  while(t--)  {    ll num=0;    scanf("%lld %lld",&n,&m);    for(int i=0;prime[i]<=n&&i
            
             n个数字中，所有素数的个数（包括重复） { num=num+n/prime[i]; } printf("%lld\n",q_pow(2,num,m)); } return 0;}