RT，我在上一个帖子的基础上大力卡常，本地能跑$<10s$（spoj上20s时限），但是spoj上还是过不去。

Code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
map<pair<ll,ll>,ll> mp;
map<ll,ll> pip; 
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<=block){
		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<=block){
		return pi[x];
	}
	if(x<=1e9){
		int cur=lower_bound(b+1,b+r+2,x)-b;
		if(b[cur]!=x){
			cur--;
		}
		return cur;
	}
	if(pip[x]){
		return pip[x];
	}
	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 pip[x]=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,ans=1,xs;
		n=read(),m=read();
		if(mp[make_pair(n,m)]){
			write(mp[make_pair(n,m)]);
			printf("\n");
			continue;
		}
		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;
			}
	    }
	    mp[make_pair(n,m)]=ans;
	    write(ans);
	    printf("\n");
	}
	return 0;
}