前缀素数和

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 222222

ll n,Sqr,w[MAX];
ll pri[MAX],id1[MAX],id2[MAX],h[MAX],g[MAX],m;
bool zs[MAX];
int tot,sp[MAX];
ll MOD;
const int N = 1000010;

typedef long long LL;

namespace Min25
{

    int prime[N], id1[N], id2[N], flag[N], ncnt, m;

    LL g[N], sum[N], a[N], T, n;

    inline int ID(LL x)
    {
        return x <= T ? id1[x] : id2[n / x];
    }

    inline LL calc(LL x)
    {
        return x * (x + 1) / 2 - 1;
    }

    inline LL f(LL x)
    {
        return x;
    }

    inline void init()
    {
        T = sqrt(n + 0.5);
        ncnt=0;
        m=0;
        for (int i = 2; i <= T; i++)
        {
            if (!flag[i])
                prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
            for (int j = 1; j <= ncnt && i * prime[j] <= T; j++)
            {
                flag[i * prime[j]] = 1;
                if (i % prime[j] == 0)
                    break;
            }
        }
        for (LL l = 1; l <= n; l = n / (n / l) + 1)
        {
            a[++m] = n / l;
            if (a[m] <= T)
                id1[a[m]] = m;
            else
                id2[n / a[m]] = m;
            g[m] = calc(a[m]);
        }
        for (int i = 1; i <= ncnt; i++)
            for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++)
                g[j] = g[j] - (LL)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
    }

    inline LL solve(LL x)
    {
        if (x <= 1)
            return x;
        return n = x, init(), g[ID(n)];
    }
}

ll qpow( ll x,ll y ,ll mod )
{
    ll res=1;
    while( y )
    {
        if(  y& 1 ) res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}

int main()
{
    //cout<<Min25::solve(1e6);
    int t;
    scanf("%d",&t);// (n<=1e11 求 1-n的素数和 ) 
    while( t-- )
    {    
        scanf("%lld%lld",&n,&MOD);
        ll psum=Min25::solve(n)%MOD;
    }
}

前缀素数个数和

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e6+10;
ll a[N],g[N],prime[N],cnt,sq,id;
ll Min_25(ll n){
  auto ID=[&](ll x){
    return x<=sq?x:id-n/x+1;
  };
  id=cnt=0,sq=sqrt(n);
  for(ll i=1;i<=n;i=a[id]+1){
    a[++id]=n/(n/i);
    g[id]=a[id]-1;
  }
  for(int i=2;i<=sq;i++){
    if(g[i]==g[i-1])continue;
    prime[++cnt]=i;
    ll pp=1ll*i*i;
    for(int j=id;a[j]>=pp;j--){
      g[j]-=(g[ID(a[j]/i)]-(cnt-1));
    }
  }
  return g[id];
}

int main()
{
    cout<<Min_25(1e6);
}