Min25 筛
求解 \(1-N\) 的质数和，其中 \(N \le 10^{10}\) 。
namespace min25{const int N = 1000000 + 10;int prime[N], id1[N], id2[N], flag[N], ncnt, m;LL g[N], sum[N], a[N], T;LL n;LL mod;inline LL ps(LL n,LL k) {LL r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}void finit(){ // 最开始清0memset(g, 0, sizeof(g));memset(a, 0, sizeof(a));memset(sum, 0, sizeof(sum));memset(prime, 0, sizeof(prime));memset(id1, 0, sizeof(id1));memset(id2, 0, sizeof(id2));memset(flag, 0, sizeof(flag));ncnt = m = 0; }int ID(LL x) {return x <= T ? id1[x] : id2[n / x];}LL calc(LL x) {return x * (x + 1) / 2 - 1;}LL init(LL x) {T = sqrt(x + 0.5);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 <= x; l = x / (x / l) + 1) {a[++m] = x / l;if (a[m] <= T) id1[a[m]] = m; else id2[x / 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]);}LL solve(LL x) {if (x <= 1) return x;return n = x, init(n), g[ID(n)];}
}using namespace min25;int main() {// while (1) {int tt;scanf("%d",&tt);while(tt--){finit();scanf("%lld%lld", &n, &mod);LL ans = (n + 3) % mod * n % mod * ps(2 , mod - 2) % mod + solve(n + 1) - 4;// cout << solve(n) << endl;// ans = (ans + mod) % mod;ans = (ans + mod) % mod;printf("%lld\n", ans); }// }
}