题目：P3768 简单的数学题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

代码：

 #define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
using namespace std;
#define  LL long long 
const int N = 8e6 + 10;
const double PI = acos(-1);
LL mod = 998244353;
LL n,a[N], su[N], phi[N],cn,inv;
map<LL, LL> mpp;
LL quick(LL a, LL b, LL mod)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
void init()
{
    inv = quick(6, mod - 2, mod);
    a[0] = a[1] = phi[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!a[i]) su[++cn] = i, phi[i] = i - 1;
        for (LL j = 1; (LL)su[j] * i < N; j++)
        {
            LL mp = su[j];
            a[mp * i] = 1;
            if (i % mp == 0)
            {
                phi[i * mp] = phi[i] * mp;
                break;
            }
            phi[i * mp] = phi[i] * (mp - 1);
        }
    }
    for (LL i = 1; i < N; i++)
        phi[i] = (phi[i] * i % mod * i % mod + phi[i - 1]) % mod;
}
LL s2(LL x)
{
    x = x % mod;
    return x * (x + 1) % mod * (2 * x + 1) % mod *inv% mod;
}
LL s3(LL x)
{
    x = x % mod;
    LL res = (x * (x + 1) / 2) % mod;
    return res * res % mod;
}
LL seekp(LL n)
{
    if (n < N) return phi[n];
    if (mpp[n]) return mpp[n];
    LL ans = s3(n)%mod;
    for (LL l = 2, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        LL res = (s2(r) - s2(l - 1)) % mod;
        res = (res * seekp(n / l))%mod;
        ans = (ans - res) % mod;
    }
    ans = (ans % mod + mod) % mod;
    mpp[n] = ans;
    return ans;
}
int main() {
    
    cin >> mod >> n;
    init();
    LL ans = 0;
    for (LL l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        LL res = s3(n/l);
        LL res1 = (seekp(r) - seekp(l - 1))%mod;
        ans =(ans+ res * res1%mod) % mod;
    }
    cout << (ans%mod+mod)%mod << endl;
    return 0;
}