ccpc网络赛——Graph Theory Class（min_25筛）_综合

题意

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

优化 $∑i=3n+1i+∑p=3n+1p\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")
#include<bits/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
template<typename T> inline T fetch(){
    T ret;cin >> ret;return ret;}
template<typename T> inline vector<T> fetch_vec(int sz){
    vector<T> ret(sz);for(auto& it: ret)cin >> it;return ret;}
template<typename T> inline void makeUnique(vector<T>& v){
    sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}
template<typename T> inline T max_(T a,T b){
    if(a>b)return a;return b;}
template<typename T> inline T min_(T a,T b){
    if(a<b)return a;return b;}
void file()
{
    
#ifdef ONLINE_JUDGE
#elsefreopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);freopen("D:/LSNU/codeforces/duipai/WA.txt","w",stdout);
#endif
}
void Match()
{
    
#ifdef ONLINE_JUDGE
#elseDebug::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;cin>>t;while(t--){
    ll n,k;cin>>n>>k;a.Init();ll ans = 0;if (n >= 2) {
    ll l=n+2,r=n+1;if(l%2)r/=2;elsel/=2;ans+=r%k*(l%k)%k-5;ans=(ans%k+k+a.solve(n+1)%k)%k;}cout << ans << '\n';}Match();return 0;
}