本文主要是介绍P3768 简单的数学题(莫比乌斯反演+杜教筛)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：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;
}
这篇关于P3768 简单的数学题(莫比乌斯反演+杜教筛)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
