1002：http://acm.hdu.edu.cn/showproblem.php?pid=6889\
题意：给你一个有n个点的图，结点编号1-n。节点i和j之间的边缘权重大小是lcm（i+1，j+1）。要你给出最小生成树的所有边缘的权重的和。
思路：不妨假设i<j。两点之间的边缘权重既然是lcm（i+1，j+1）。对于j+1是合数的边，我们只要让它连在它的质因数节点上就可以最小化lcm（i+1，j+1），这个值就是j+1。那么如果是质数呢？ 很明显，直接和i=1连接，这时候它的边缘权重就是（j+1）*2。和其他的点链接边缘权重都一定比这个大。那么这么一来答案就是（3~ n+1）中所有质数的两倍再加上所有合数。再来化简，这个答案就是所有（3~ n+1）的质数的和加上（3~ n+1）的所有数的和。这时候就考虑用什么方法来求所有质数的和了。一看数据1e10，这时候发现欧拉筛已经不行了，于是打开baidu，输入百亿以内质数的和，你可以发现 知乎 上有一些方法求十亿以内的和只要0.057秒！！！，只要拿过来改改就是答案了。接着这题就不再有任何难度了。（嘘，当时找到的时候，我和两个队友都懵了，觉得这根本不是算法，而是魔法）

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


const int maxn = 1000010;
int prime[maxn], id1[maxn], id2[maxn], flag[maxn], ncnt, m;

ll g[maxn], sum[maxn], a[maxn], T, n;

namespace Min25 {
    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)];
    }

}
int main()
{
    int t;
    cin>>t;
    ll nnn,kkk;
    while(t--)
    {

        cin>>nnn>>kkk;
        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));
        T = 0; n = 0; ncnt = 0; m = 0;

        cout<<( (Min25::solve(nnn+1)-2)%kkk   +  (((nnn+1+3)%kkk)*((nnn-1)%kkk)/2)%kkk )  %kkk <<endl;
        //这个就是计算3~n+1的质数的和 与 3~n+1 的所有数的和
    }
    return 0;
}