《hdu6889》

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e6+5;
const int M = 1e6+5;
//const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e18
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < ‘0‘ || c > ‘9‘){if(c == ‘-‘) f = -1;c = getchar();}
        while(c >= ‘0‘ && c <= ‘9‘){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar(‘-‘);}
        if(x > 9) print(x/10);
        putchar(x%10+‘0‘);
    }
}
using namespace FASTIO;

LL sum1[N],prime[N],id1[N],id2[N],g1[N],g2[N],w[N],Mod;
LL n,Sqr,tot = 0,m = 0;
bool flag[N];
inline LL f1(LL x)//F[i] = i的前缀和
{
    return (x + 1) * x / 2 - 1;
}
inline LL getid(LL x)//找到x的离散化对应位置
{
    if(x <= Sqr) return id1[x];
    else return id2[n/x];
}
inline void init()
{
    Sqr = sqrt(n + 0.5);
    m = 0,tot = 0;
    for(int i = 2;i <= Sqr;++i)
    {
        if(!flag[i])
        {
            prime[++tot] = i;
            sum1[tot] = (sum1[tot-1]+i) % Mod;
        }
        for(int j = 1;j <= tot && prime[j]*i <= Sqr;++j)
        {
            flag[i*prime[j]] = 1;
            if(i%prime[j] == 0) break;
        }
    }
    for(LL L = 1,r;L <= n;L = r+1)//预处理g(n,0)
    {
        r = (n/(n/L)),w[++m] = (n/L);
        if(w[m] <= Sqr) id1[w[m]] = m;
        else id2[n / w[m]] = m;
        g1[m] = f1(w[m]);
    }
    for(int i = 1;i <= tot;++i){//预处理到sqrt(n)，即tot即可
        for(int j = 1;j <= m && prime[i] * prime[i] <= w[j];++j){
            g1[j] = g1[j] - prime[i] * (g1[getid(w[j] / prime[i])] - sum1[i-1]);
        }
    }
}
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        n = read(),Mod = read();
        if(n == 1) printf("0\n");
        else if(n == 2) printf("%lld\n",6 % Mod);
        else
        {
            n++;
            init();
            LL ans =  g1[getid(n)]-2;
            n %= Mod;
            LL ma = 1LL * (n+3) * (n-2) / 2 % Mod;
            ma = (ma + ans) % Mod;
            printf("%lld\n",ma);
        }
    }
    //system("pause");
    return 0;
}