题目传送门
题目大意
令,求
思路
则原式等于
用莫比乌斯函数和的卷积替换一下
枚举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); }