本文主要是介绍P9238 [蓝桥杯 2023 省 A] 翻转硬币(杜教筛+莫比乌斯)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：https://www.luogu.com.cn/problem/P9238
思路：
代码：
#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 = 1e7+ 10;
const double PI = acos(-1);
LL mod = 998244353;
LL n, mu[N], su[N], a[N], cn;
unordered_map<LL, LL> mpu;
void init()
{
mu[1] = a[1] = 1;
for (int i = 2; i < N; i++)
{
if (!a[i]) su[++cn] = i, mu[i] = -1;
for (int j = 1; (LL)su[j] * i < N; j++)
{
LL mp = su[j];
a[i * mp] = 1;
if (i % mp == 0)
{
mu[mp * i] = 0;
break;
}
mu[i * mp] = mu[i] * -1;
}
}
for (int i = 1; i < N; i++) mu[i] += mu[i - 1];
}
LL seekmu(LL n)
{
if (n < N) return mu[n];
if (mpu[n]) return mpu[n];
LL ans = 1;
for (LL l = 2, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans -=(r-l+1)*seekmu(n/l);
}
mpu[n] = ans;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
init();
LL ans = 0;
cin >> n;
LL m = sqrtl(n);
for (LL l = 1, r; l <= m; l = r + 1)
{
r = sqrtl(n / (n / (l*l)));
ans += (n / (l * l))*(seekmu(r) - seekmu(l-1));
}
cout << ans << endl;
return 0;
}
这篇关于P9238 [蓝桥杯 2023 省 A] 翻转硬币(杜教筛+莫比乌斯)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
