P9238 [蓝桥杯 2023 省 A] 翻转硬币(杜教筛+莫比乌斯)

题index.php/tags-41973.html" >���：https://www.luogu.com.cn/problem/P9238

思路：

代码：

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

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 mpu;

void init()

{

    mu[1] = a[1] = 1;

    for (int i = 2; i

    {

        if (!a[i]) su[++cn] = i, mu[i] = -1;

        for (int j = 1; (LL)su[j] * i

        {

            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

}

LL seekmu(LL n)

{

    if (n

    if (mpu[n]) return mpu[n];

    LL ans = 1;

    for (LL l = 2, r; l > n;

    LL m = sqrtl(n);

    for (LL l = 1, r; l