题目传送门

题目大意

令,求

思路

则原式等于

用莫比乌斯函数和的卷积替换一下

枚举e，e为的因子，和为的倍数

e的倍数显然有个

令

这一步显然和为的两个因子，且,所以我们可以先枚举,然后枚举,这样

因为莫比乌斯函数和函数的卷积是欧拉函数所以

最后交换一下和得到

枚举T，原式等价于所有倍数的函数和
最后整除分块+杜教筛处理

AC代码

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
// const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
ll mod;
const int maxn = 1e5 + 10;
ll f[maxn];
map<int, int> ff;
int prime[maxn],tot;
bool notprime[maxn];
void init()
{
    f[1] = 1;
    notprime[0] = notprime[1] = 1;
    for (ll i = 2; i < maxn; ++i)
    {
        if (!notprime[i])
        {
            prime[tot++] = i;
            f[i] = i - 1;
        }
        for (int j = 0; j < tot && prime[j] * i < maxn; ++j)
        {
            notprime[prime[j] * i] = 1;
            if (i % prime[j] == 0)
            {
                f[prime[j] * i] = f[i] * prime[j];
                break;
            }else
            {
                f[prime[j] * i] = f[prime[j]] * f[i];
            }
        }
    }
    for (int i = 1; i < maxn; ++i)
    {
        (f[i] += f[i - 1]) %= mod;
    }
}
ll getpre(ll x)
{
    if(x<maxn)
        return f[x];
    if(ff.count(x))
        return ff[x];
    ll res = x * (x + 1) / 2 % mod;
    for (int l = 2, r; l <= x; l = r + 1)
    {
        r = (x / (x / l));
        res = (res - (r - l + 1) * getpre(x / l) % mod + mod) % mod;
    }
    return ff[x] = res;
}
ll qmod(ll a,ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n&1)
            ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
ll inv6;
ll sqsum(ll x)
{
    return x * (x + 1) % mod * (2 * x + 1) % mod * inv6 % mod;
}
int main()
{
    int n;
    read(n), read(mod);
    init();
    inv6 = qmod(6, mod - 2);
    ll res = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        res = (res + (sqsum(r) - sqsum(l - 1) + mod) % mod * getpre(n / l) % mod) % mod;
    }
    printf("%lld\n", res);
}