题目

思路

Code：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
int b[60000005],mark[600005],p[35][5],cur,pi[600005],sz[5],mrk_cnt,r,K=1959,block=2*3*5*7*11*13*17,M=7,sum=0;
bool a[510517],d[510517],e[510517];
void shai(int n){
	a[0]=a[1]=true;
	for(int i=1;i<block;i++){
		e[i]=true;
	}
	for(int i=2;i<=block;i++){
		if(!a[i]){
			b[++r]=i;
			if(r<=M){
				e[i]=false;
			}
		}
		pi[i]=r;
		for(int j=1;j<=r&&i*b[j]<=block;j++){
			a[i*b[j]]=true;
			if(j<=M){
				e[i*b[j]]=false;
			}
			if(i%b[j]==0){
				break;
			}
		}
	}
	for(int i=1;i<block;i++){
		if(e[i]){
			mark[++mrk_cnt]=i;
		}
	}
	int st,en;
	for(int i=1;i<K;i++){
		st=i*block;en=(i+1)*block-1;		
		memcpy(d,e,sizeof(bool)*block);
		for(int j=M+1;b[j]*b[j]<=en;j++){
			int beg,ene;
			beg=max((st-1)/b[j]+1,b[j])*b[j];
			ene=b[j]<<1;
			if(!(beg&1)){
				beg+=b[j];
			}
			for(int k=beg-st;k<block;k+=ene){
				d[k]=false;
			}
		}
		for(int j=1;j<=mrk_cnt;j++){
			if(d[mark[j]]){
				b[++r]=mark[j]+st;
			}
		}
	}
}
inline void write(__int128 x){
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
ll getphi(ll x,int s){
	if(!s){
		return x;
	}
	if(s<=2){
		return p[x%sz[s]][s]+(x/sz[s])*p[sz[s]][s];
	}
	if(x<=b[s]*b[s]){
		return pi[x]-s+1;
	}
	if(x<=b[s]*b[s]*b[s]&&x<9000){
		int sx=pi[int(pow(x,1.0/2.0))];
        ll ans=pi[x]-(sx+s-2)*(sx-s+1)/2;
        for (int i=s+1;i<=sx;i++) {
        	ans+=pi[x/b[i]];
		}
        return ans;
	}
	return getphi(x,s-1)-getphi(x/b[s],s-1);
}
ll getpi(ll x){
	if(x<9000){
		return pi[x];
	}
	ll ans=getphi(x,pi[ll(pow(x,1.0/3.0))])+pi[ll(pow(x,1.0/3.0))]-1;
	for(ll i=pi[ll(pow(x,1.0/3.0))],ed=pi[ll(pow(x,1.0/2.0))];i<=ed;i++){
		ans-=getpi(x/b[i]);
	}
	return ans;
}
inline __int128 read(){
    __int128 x(0),f(1);
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
ll ssx(ll x){
	if(x<9000){
		return pi[x];
	}
	if(x<=1e9){
		int cur=lower_bound(b+1,b+r+1,x)-b;
		if(b[cur]!=x){
			cur--;
		}
		return cur;
	}
	int a,bx,c;
	a=ssx(int(pow((int)(pow(x,1.0/2.0)),1.0/2.0)));
	bx=ssx(int(pow(x,1.0/2.0)));
	c=ssx(int(pow(x,1.0/3.0)));
	ll sum=getphi(x,a)+(ll)(bx+a-2)*(bx-a+1)/2;
	for(int i=a+1;i<=bx;i++){
		ll w=x/b[i];
		sum-=ssx(w);
		if(i>c){
			continue;
		}
		ll lim=ssx(int(pow(w,1.0/2.0)));
		for(int j=i;j<=lim;j++){
			sum-=ssx(w/b[j])-(j-1);
		}
	}
	return sum;
}
__int128 pre(__int128 x,long long s,__int128 k){
	__int128 ans=1;
	while(s){
		if(s&1){
			ans=(ans*x)%k;
		}
		x=(x*x)%k;
		s>>=1;
	}
	return ans;
}
int main(){
	shai(1e9);
	sz[0]=1;
	b[r+1]=2e9;
	for(int i=0;i<=30;i++){
		p[i][0]=i;
	}
	for(int i=1;i<=2;i++){
		sz[i]=sz[i-1]*b[i];
		for(int j=1;j<=30;j++){
			p[j][i]=p[j][i-1]-p[j/b[i]][i-1];
		}
	}
	ll t;
	cin>>t;
	while(t--){
		__int128 n,m,x,lar=-1,las=0,ans=1,xs;
		n=read(),m=read();
		x=(long long)(sqrt((long long)n));
		for(int i=1;b[i]<=x;i++){
	        ll tmp=0,p=b[i];
	        while(p<=n){
	        	tmp=(tmp+n/p)%m,p*=b[i];
			}
	    	ans=ans*(tmp+1)%m;
	    }
		for(__int128 l=x+1,r=0;l<=n;l=r+1){
	    	r=n/(n/l);
	    	if(lar==-1){
	    		lar=ssx(r);
	    		ans=(ans*pre(n/l+1,(lar-ssx(l-1)),m))%m;
			}
			else{
				xs=ssx(r);
				ans=(ans*pre(n/l+1,(xs-lar),m))%m;
				lar=xs;
			}
			las=r;
	    }
	    write(ans);
	    printf("\n");
	}
	return 0;
}