HDU 6889 Graph Theory Class（min_25求素数前缀和）

题意：给定数n，表示有n个值从1-n的点，求最小生成树。其中边的权值表示为lcm（x+1,y+1）。
设一点的值为x。x>=3时，若x为素数，则能找到的最小边为与点1的连边，权值为2*x；若为合数，则一定可以找到一个因数y+1，使得权值为lcm(x+1,y+1)=x+1。
因此只要求2到n+1的和，再加上该区间的素数和即可。
数据范围很大（1e10），普通的筛法会时间和内存都不够。现在我已知的方法有两种，第一个是分块打表，第二个是用min25筛。在这里使用min25筛，思想可以参照https://blog.csdn.net/qq_39972971/article/details/81543972

#include <bits/stdc++.h>using namespace std;const int N = 1000010;typedef long long LL;
LL TT,nn,k;
namespace Min25 {
    int prime[N], id1[N], id2[N], flag[N], ncnt, m;LL g[N], sum[N], a[N], T, n;inline void fff(){
    for(int i=0;i<=N;i++){
    prime[i]=0;id1[i]=0;id2[i]=0;flag[i]=0;g[i]=0;sum[i]=0;a[i]=0;}ncnt=0;m=0;T=0;n=0;}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);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)];}}void extend_gcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0) {
    x=1,y=0;return;}extend_gcd(b,a%b,x,y);LL tmp=x;x=y;y=tmp-(a/b)*y;
}
LL mod_inverse(LL a,LL m)
{
    LL x,y;extend_gcd(a,m,x,y);return (m+x%m)%m;
}
int main()
{
    LL sum;cin>>TT;while(TT--){
    sum=0;scanf("%lld%lld",&nn,&k);LL a=mod_inverse(2,k);//cout<<a<<endl;sum=(((((nn+3)%k)*((nn)%k))%k)*a)%k-2;//cout<<sum<<endl;Min25::fff();sum=(sum+Min25::solve(nn+1)-2)%k;printf("%lld\n",sum%k);}return 0;
}