ccpc网络赛——Graph Theory Class（min

2020-12-22互联技术发消息

题意

构造最小生成树，边权lcm(i+1,j+1);

解析

优化 $\sum_{i=3}^{n+1}i+\sum_{p=3}^{n+1}{p}$
1e10质数min_25筛

赛前评测机快，上__int128还行，赛后就老老实实优化常数吧

//#pragma comment(linker,"/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
//#pragma GCC target ("sse4")
#includebits/stdc++.h
//typedef long long ll;
#define ull         unsigned long long
//#define int       __int128
//#define int         long long
#define F           first
#define S           second
#define endl        "\n"//flush
#define eps         1e-6
#define base        131
#define lowbit(x)   (x(-x))
#define db          double
#define PI          acos(-1.0)
#define inf         0x3f3f3f3f
#define MAXN        0x7fffffff
#define INF         0x3f3f3f3f3f3f3f3f
#define _for(i, x, y) for (int i = x; i = y; i++)
#define for_(i, x, y) for (int i = x; i = y; i--)
#define ferma(a,b)  pow(a,b-2)
#define mod(x)      (x%mod+mod)%mod
#define pb          push_back
#define decimal(x)  cout  fixed  setprecision(x);
#define all(x)      x.begin(),x.end()
#define rall(x)      x.rbegin(),x.rend()
//#define memset(a,b) memset(a,b,sizeof(a));
#define IOS         ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
#ifndef ONLINE_JUDGE
#include "local.h"
#endif
templatetypename T inline T fetch(){T ret;cin  ret;return ret;}
templatetypename T inline vectorT fetch_vec(int sz){vectorT ret(sz);for(auto it: ret)cin  it;return ret;}
templatetypename T inline void makeUnique(vectorT v){sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}
templatetypename T inline T max_(T a,T b){if(ab)return a;return b;}
templatetypename T inline T min_(T a,T b){if(ab)return a;return b;}
void file()
{
#ifdef ONLINE_JUDGE
#else
    freopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);
    freopen("D:/LSNU/codeforces/duipai/WA.txt","w",stdout);
#endif
}
void Match()
{
#ifdef ONLINE_JUDGE
#else
    Debug::Compare();
#endif // ONLINE_JUDGE
}
typedef long long ll;
const int N = 1000010;
struct Min25 {

    ll 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() {
        memset(prime, 0, sizeof(prime));
        memset(id1, 0, sizeof(id1));
        memset(id2, 0, sizeof(id2));
        memset(flag, 0, sizeof(flag));
        memset(g, 0, sizeof(g));
        memset(sum, 0, sizeof(sum));
        memset(a, 0, sizeof(a));
        ncnt = m = T = n = 0;
    }
    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)];
    }

}a;
signed main()
{
    IOS;
    file();
    int t;
    cint;
    while(t--)
    {
        ll n,k;
        cinnk;
        a.Init();
        ll ans = 0;
        if (n = 2) {
            ll l=n+2,r=n+1;
            if(l%2)
                r/=2;
            else
                l/=2;
            ans+=r%k*(l%k)%k-5;
            ans=(ans%k+k+a.solve(n+1)%k)%k;
        }
        cout  ans  '\n';

    }



    Match();
    return 0;
}