B: Graph Theory Class

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6889
伪图论题，板子找的好就能A。
大概要求出这个东西：
lcm(2,3)+min(lcm(2,4),lcm(3,4))+min(lcm(2,4),lcm(3,4))+min(lcm(2,5),lcm(3,5),lcm(4,5))...
我们可以通过唯一分解定理的思路来取min，从i=3开始，若是一个质数，那么lcm取min后肯定是2*i，若不是一个质数，那么肯定为这个数自己，因此，我们的目标就是求i=3开始到n+1(注意)的数的和加上i=3开始的质数的和。鉴于n=1e11，直接套板子。
值得注意的是n为1e11，那么利用求和公式求和的时候别忘了一步一取模。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;

int mod;

inline ll add_mod(ll x, ll y) {
    return (x + y >= mod) ? (x + y - mod) : (x + y);
}

inline ll sub_mod(ll x, ll y) {
    return (x < y) ? (x - y + mod) : (x - y);
}

inline ll mul_mod(ll x, ll y) {
    return x * y % mod;
}

inline ll sum(ll n) {
    n %= mod;
    return (n * (n + 1)) / 2 % mod;
}
inline ll q_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1; 
    } 
    return ans;
}

const int MAXN = 1e6 + 5;

ll ssum[MAXN];
ll lsum[MAXN];
bool mark[MAXN];

ll prime_sum(ll n) {
    const int v = sqrt(n);
    ssum[0] = 0;
    lsum[0] = 0;
    memset(mark, 0, sizeof(mark[0]) * (v + 1));
    for(ll i = 1; i <= v; ++i) {
        ssum[i] = sum(i) - 1;
        lsum[i] = sum(n / i) - 1;
    }
    for(ll p = 2; p <= v; ++p) {
        if(ssum[p] == ssum[p - 1])
            continue;
        ll psum = ssum[p - 1];
        ll q = p * p;
        ll ed = min((ll)v, n / q);
        ll delta1 = (p & 1) + 1;
        for(ll i = 1; i <= ed; i += delta1) {
            if(!mark[i]) {
                ll d = i * p;
                ll tmp = (d <= v) ? lsum[d] : ssum[n / d];
                tmp = sub_mod(tmp, psum);
                tmp = mul_mod(tmp, p);
                lsum[i] = sub_mod(lsum[i], tmp);
            }
        }
        ll delta2 = p * delta1;
        for(ll i = q; i <= ed; i += delta2)
            mark[i] = 1;
        for(ll i = v; i >= q; --i) {
            ll tmp = ssum[i / p];
            tmp = sub_mod(tmp, psum);
            tmp = mul_mod(tmp, p);
            ssum[i] = sub_mod(ssum[i], tmp);
        }
    }
    return lsum[1];
}

signed main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n >> mod;
        int inv2 = q_pow(2, mod-2);
        int ans1 = (n+4)%mod*(n-1)%mod*inv2%mod;
        int ans2 = (prime_sum(n+1)-2 + mod )%mod;
        cout << (ans1+ans2)%mod << endl;
    }
}