题解 | #欧拉筛#

//大于P的质数的阶乘对P求余等于0
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int prim[N],a[N];  //a[ i ]用来存i是不是质数，等于0为质数
int t,n,p;
void primes()   //欧拉筛求质数，最快的方法
{
    int cnt=0;
    for(int i=2;i<=N;i++)
    {
        if(!a[i])prim[cnt++]=i;
        for(int j=0;prim[j]<=N/i;j++)
        {
            a[prim[j]*i]=1;
            if(i%prim[j]==0)break;
        }
    }
}
int main()
{
    primes();
    scanf("%d",&t);
    while(t--)
    {
        ll s=1,sum=0;
        scanf("%d%d",&n,&p);
        for(int i=2;i<=min(n,p);i++)   //从2枚举到min(n,p)
        {
            s=(s*i)%p;  //s是阶乘,要开long long
            if(!a[i])
              sum=(sum+s)%p;  //sum是结果
        }
        
        cout<<sum<<endl;
    }
    
    return 0;
}