标签：return int res mu lw P4165 define

莫比乌斯函数 #筛法 #gcd #数学

一定选 \(k\) 的倍数，原题目等价于 \([\frac{l}{k},\frac{r}{k}]\) ，选择 \(n\) 次，最后 \(gcd=1\)

考虑容斥去算，注意到超过 \(10^5\) 的质数的影响不好处理，但是因为区间长度，大于 \(10^5\) 的质数只会选择 \(n\) 次本身，所以考虑一开始容斥的时候就将所有选择一样数的情况去掉，最后特判 \(l\leq k\)
的情况

时间复杂度是筛法的

// Author: xiaruize
#ifndef ONLINE_JUDGE
bool start_of_memory_use;
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int n, k, lw, hi;
int res = 0;

int mu[100005];
bool isnp[100005];
vector<int> primes;

void init(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i), mu[i] = -1;
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
            {
                mu[p * i] = 0;
                break;
            }
            else
                mu[p * i] = mu[p] * mu[i];
        }
    }
}

void solve()
{
    cin >> n >> k >> lw >> hi;
    lw = (lw + k - 1) / k;
    hi = hi / k;
    if (lw > hi)
    {
        cout << "0" << endl;
        return;
    }
    int res = 0;
    init(1e5);
    rep(i, 1, 1e5)
    {
        if (hi / i < (lw + i - 1) / i)
            break;
        res = ((mu[i] * (qpow(hi / i - (lw + i - 1) / i + 1, n) - (hi / i - (lw + i - 1) / i + 1) % MOD) % MOD + res) % MOD + MOD) % MOD;
    }
    if (lw == 1)
        res = (res + 1) % MOD;
    cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：return,int,res,mu,lw,P4165,define
From： https://www.cnblogs.com/xiaruize/p/18105726