莫比乌斯系列
莫比乌斯函数
定义
\[\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & n 含有平方因子 \\ (-1)^k & k 为 n 的本质不同质因子个数\end{cases} \]性质
- \(\sum_{d | n} \mu(d) = [n = 1]\) ，即 \(\mu * 1 = \epsilon\) 。
- \(\varphi(n) = \sum_{d | n} \mu(d) \times \dfrac{n}{d}\) ，即 \(\mu * id = \varphi\) 。
求法
单个数
inline int Mu(int n) {
int mu = 1;
for (int i = 2; i * i <= n; ++i)
if (!(n % i)) {
if (!(n % (i * i)))
return 0;
mu *= -1, n /= i;
}
if (n > 1)
mu *= -1;
return mu;
}
线性筛
inline void sieve(int n) {
memset(isp, true, sizeof(isp));
isp[1] = false, mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (isp[i])
pri[++pcnt] = i, mu[i] = -1;
for (int j = 1; j <= pcnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
mu[i * pri[j]] = -mu[i];
else {
mu[i * pri[j]] = 0;
break;
}
}
}
}
杜教筛
namespace Mu {
map<int, ll> mp;
ll f[N], sum[N];
inline void prework() {
for (int i = 1; i < N; ++i)
sum[i] = sum[i - 1] + f[i];
}
ll Sum(ll n) {
if (n < N)
return sum[n];
if (mp.find(n) != mp.end())
return mp[n];
ll res = 1;
for (ll l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res -= 1ll * (r - l + 1) * Sum(n / l);
}
return mp[n] = res;
}
} // namespace Mu
莫比乌斯反演
设 \(f(n), g(n)\) 为两个数论函数，由 \(\mu * 1 = \epsilon\) ，得到：
\[f = f * \epsilon = f * (\mu * 1) = (f * 1) * \mu \]形式一
设 \(f(n), g(n)\) 为两个数论函数，则：
\[f(n) = \sum_{d | n} g(d) \iff g(n) = \sum_{d | n} f(d) \mu(\dfrac{n}{d}) \]此时 \(f(n)\) 称为 \(g(n)\) 的莫比乌斯变换，\(g(n)\) 称为 \(f(n)\) 的莫比乌斯逆变换，即莫比乌斯反演。
形式二
设 \(f(n), g(n)\) 为两个数论函数，则：
\[f(n) = \sum_{n | d} g(d) \iff g(n) = \sum_{n | d} f(d) \mu(\dfrac{d}{n}) \]常见应用
形式一
\[\begin{align} &\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = 1] \\ =& \sum_{i = 1}^n \sum_{j = 1}^m \sum_{d | i} \sum_{d | j} \mu(d) \\ =& \sum_{d = 1}^n \mu(d) \sum_{i = 1}^n \sum_{j = 1}^m [d | i] [d | j] \\ =& \sum_{d = 1}^n \mu(d) \lfloor \dfrac{n}{d} \rfloor \lfloor \dfrac{m}{d} \rfloor \end{align} \]数论分块即可做到 \(O(n) - O(\sqrt{n})\) 。
形式二
\[\begin{align} & \sum_{i = 1}^n \sum_{j = 1}^m f(\gcd(i, j)) \\ =& \sum_{d = 1}^n f(d) \sum_{i = 1}^{n} \sum_{j = 1}^{m} [\gcd(i, j) = d] \\ =& \sum_{d = 1}^n f(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i, j) = 1] \\ =& \sum_{d = 1}^n f(d) \sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(k) \lfloor \dfrac{n}{d k} \rfloor \lfloor \dfrac{m}{d k} \rfloor \end{align} \]令 \(d k = T\) ，则：
\[= \sum_{T = 1}^n \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum_{d | T} f(d) \mu(\dfrac{T}{d}) \]数论分块即可做到 \(O(n) - O(\sqrt{n})\) 。
扩展
对于数论函数 \(f, g\) 与完全积性函数 \(t\) 且满足 \(t(1) = 1\) ，则：
\[f(n) = \sum_{i = 1}^n t(i) g(\lfloor \dfrac{n}{i} \rfloor) \iff g(n) = \sum_{i = 1}^n \mu(i) t(i) f(\lfloor \dfrac{n}{i} \rfloor) \]证明：
\[\begin{align} g(n) &= \sum_{i = 1}^n \mu(i) t(i) f(\lfloor \dfrac{n}{i} \rfloor) \\ &= \sum_{i = 1}^n \mu(i) t(i) \sum_{j = 1}^{\lfloor \frac{n}{i} \rfloor} t(j) g(\lfloor \dfrac{n}{ij} \rfloor) \\ &= \sum_{T = 1}^n \sum_{i = 1}^n \mu(i) t(i) \sum_{j = 1}^{\lfloor \frac{n}{i} \rfloor} [ij = T] t(j) g(\lfloor \dfrac{n}{T} \rfloor) \\ &= \sum_{T = 1}^n \sum_{i | T} \mu(i) t(i) t(\dfrac{T}{i}) g(\lfloor \dfrac{n}{T} \rfloor) \\ &= \sum_{T = 1}^n g(\lfloor \dfrac{n}{T} \rfloor) t(T) \sum_{i | T} \mu(i) \\ &= g(n) t(1) \end{align} \]应用
\[\begin{aligned} &\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) \in prime] \\ =& \sum_{k = 1}^n [k \in prime] \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = k] \\ =& \sum_{k = 1}^n [k \in prime] \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i, j) = 1] \\ =& \sum_{k = 1}^n [k \in prime] \sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor \mu(d) \end{aligned} \]P2257 YY的GCD PGCD - Primes in GCD Table
求：
\[\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) \in prime] \]\(n, m \leq 10^7\)
设 \(T = dk\) ，则：
\[\begin{aligned} &= \sum_{k = 1}^n [k \in prime] \sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \mu(d) \\ &= \sum_{T = 1}^n \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum_{k | T, k \in prime} \mu(\dfrac{T}{k}) \end{aligned} \]\(n = m\) 的弱化版是这题：P2568 GCD
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e7 + 7;
ll f[N], sum[N];
int pri[N], mu[N];
bool isp[N];
int T, n, m, pcnt;
inline void sieve() {
memset(isp, true, sizeof(isp));
mu[1] = 1, isp[1] = false;
for (int i = 2; i < N; ++i) {
if (isp[i])
pri[++pcnt] = i, mu[i] = -1;
for (int j = 1; j <= pcnt && i * pri[j] < N; ++j) {
isp[pri[j] * i] = false;
if (i % pri[j])
mu[i * pri[j]] = -mu[i];
else
break;
}
}
for (int i = 1; i <= pcnt; ++i)
for (int j = 1; pri[i] * j < N; ++j)
f[j * pri[i]] += mu[j];
for (int i = 1; i < N; ++i)
sum[i] = sum[i - 1] + f[i];
}
signed main() {
sieve();
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
if (n > m)
swap(n, m);
ll ans = 0;
for (int l = 1, r = 0; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
}
printf("%lld\n", ans);
}
return 0;
}
\[\begin{align} & \sum_{i = 1}^n \sum_{j = 1}^m d(ij) \\ =& \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x | i} \sum_{y | j} [\gcd(x, y) = 1] \\ =& \sum_{x = 1}^n \sum_{y = 1}^m \lfloor \dfrac{n}{x} \rfloor \lfloor \dfrac{m}{y} \rfloor \sum_{d|x, d | y} \mu(d) \\ =& \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \dfrac{n}{id} \rfloor \lfloor \dfrac{m}{jd} \rfloor \\ =& \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \dfrac{n}{id} \rfloor \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \dfrac{m}{jd} \rfloor \\ \end{align} \]设 \(d(n)\) 表示 \(n\) 的约数个数，求：
\[\sum_{i = 1}^n \sum_{j = 1}^m d(ij) \]\(T, n, m \leq 5 \times 10^4\)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e4 + 7;
ll f[N];
int pri[N], mu[N], sum[N];
bool isp[N];
int T, n, m, pcnt;
inline void sieve() {
memset(isp, true, sizeof(isp));
isp[1] = false, mu[1] = 1;
for (int i = 2; i < N; ++i) {
if (isp[i])
pri[++pcnt] = i, mu[i] = -1;
for (int j = 1; j <= pcnt && i * pri[j] < N; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
mu[i * pri[j]] = -mu[i];
else {
mu[i * pri[j]] = 0;
break;
}
}
}
for (int i = 1; i < N; ++i)
sum[i] = sum[i - 1] + mu[i];
for (int i = 1; i < N; ++i)
for (int l = 1, r; l <= i; l = r + 1) {
r = i / (i / l);
f[i] += 1ll * (i / l) * (r - l + 1);
}
}
signed main() {
sieve();
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
if (n > m)
swap(n, m);
ll ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += f[n / l] * f[m / l] * (sum[r] - sum[l - 1]);
}
printf("%lld\n", ans);
}
return 0;
}
\[\begin{align} & \prod_{i = 1}^n \prod_{j = 1}^n \dfrac{\operatorname{lcm}(i, j)}{\gcd(i, j)} \\ =& \prod_{i = 1}^n \prod_{j = 1}^n \dfrac{ij}{\gcd(i, j)^2} \\ =& \dfrac{\prod_{i = 1}^n i \prod_{j = 1}^n j}{\prod_{i = 1}^n \prod_{j = 1}^n \gcd(i, j)^2} \\ =& \dfrac{(n!)^{2n}}{(\prod_{i = 1}^n \prod_{j = 1}^n \gcd(i, j))^2} \\ \end{align} \]求：
\[\prod_{i = 1}^n \prod_{j = 1}^n \dfrac{\operatorname{lcm}(i, j)}{\gcd(i, j)} \pmod{104857601} \]\(n \leq 10^6\)
单独考虑下面的部分得到 ：
\[\prod_{d = 1}^n d^{\sum_{i = 1}^{n} \sum_{j = 1}^{n} [\gcd(i, j) = d] \\} \]单独考虑指数部分得到：
\[\begin{align} & \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i, j) = 1] \\ =& \left( \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \left(2 \times \sum_{j = 1}^i [\gcd(i, j) = 1] \right) \right) - 1 \\ =& 2 \times \left( \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \varphi(i) \right) - 1 \\ \end{align} \]#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int Mod = 104857601;
const int N = 1e6 + 7;
int pri[N], phi[N], sum[N];
bool isp[N];
int n, pcnt;
inline int add(int x, int y) {
x += y;
if (x >= Mod)
x -= Mod;
return x;
}
inline int dec(int x, int y) {
x -= y;
if (x < 0)
x += Mod;
return x;
}
inline int mi(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % Mod)
if (b & 1)
res = 1ll * res * a % Mod;
return res;
}
inline void sieve(int n) {
memset(isp, true, sizeof(isp));
isp[1] = false, phi[1] = 1;
for (int i = 2; i <= n; ++i) {
if (isp[i])
pri[++pcnt] = i, phi[i] = i - 1;
for (int j = 1; j <= pcnt && i * pri[j] < N; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
phi[i * pri[j]] = phi[i] * phi[pri[j]];
else {
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
for (int i = 1; i <= n; ++i)
sum[i] = (sum[i - 1] + phi[i]) % (Mod - 1);
}
signed main() {
scanf("%d", &n);
sieve(n);
int fac = 1;
for (int i = 1; i <= n; ++i)
fac = 1ll * fac * i % Mod;
int ans = 1ll * mi(fac, n * 2) * fac % Mod * fac % Mod;
for (int i = 1; i <= n; ++i)
ans = 1ll * ans * mi(mi(i, 4ll * sum[n / i] % (Mod - 1)), Mod - 2) % Mod;
printf("%d", ans);
return 0;
}
\[\begin{align} & \sum_{i = 1}^{n} \sum_{j = 1}^n \sum_{p = 1}^{\lfloor \frac{n}{j} \rfloor} \sum_{q = 1}^{\lfloor \frac{n}{j} \rfloor} [\gcd(i, j) = 1] [\gcd(p, q) = 1] \\ =& \sum_{i = 1}^{n} \sum_{j = 1}^n [\gcd(i, j) = 1] \sum_{p = 1}^{n} \sum_{q = 1}^{n} [\gcd(p, q) = j] \\ =& \sum_{i = 1}^{n} \sum_{p = 1}^{n} \sum_{q = 1}^{n} [\gcd(i, p, q) = 1] \\ =& \sum_{d = 1}^n \mu(d) \lfloor \dfrac{n}{d} \rfloor^3 \end{align} \]求：
\[\sum_{i = 1}^{n} \sum_{j = 1}^n \sum_{p = 1}^{\lfloor \frac{n}{j} \rfloor} \sum_{q = 1}^{\lfloor \frac{n}{j} \rfloor} [\gcd(i, j) = 1] [\gcd(p, q) = 1] \pmod{998244353} \]\(n \leq 2 \times 10^9\)
杜教筛处理 \(\mu\) 的前缀和即可。
#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
const int N = 1e7 + 7;
map<int, int> mp;
int pri[N], mu[N], sum[N];
bool isp[N];
int n, pcnt;
inline int add(int x, int y) {
x += y;
if (x >= Mod)
x -= Mod;
return x;
}
inline int dec(int x, int y) {
x -= y;
if (x < 0)
x += Mod;
return x;
}
inline void sieve() {
memset(isp, true, sizeof(isp));
isp[1] = false, mu[1] = 1;
for (int i = 2; i < N; ++i) {
if (isp[i])
pri[++pcnt] = i, mu[i] = Mod - 1;
for (int j = 1; j <= pcnt && i * pri[j] < N; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
mu[i * pri[j]] = Mod - mu[i];
else {
mu[i * pri[j]] = 0;
break;
}
}
}
for (int i = 1; i < N; ++i)
sum[i] = add(sum[i - 1], mu[i]);
}
int Sum(int n) {
if (n < N)
return sum[n];
if (mp.find(n) != mp.end())
return mp[n];
int res = 1;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res = dec(res, 1ll * (r - l + 1) * Sum(n / l) % Mod);
}
return mp[n] = res;
}
signed main() {
sieve();
scanf("%d", &n);
int ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = add(ans, 1ll * (n / l) * (n / l) % Mod * (n / l) % Mod * dec(Sum(r), Sum(l - 1)) % Mod);
}
printf("%d", ans);
return 0;
}
\[\begin{align} & \sum_{i = 1}^n \sum_{j = 1}^n ij \gcd(i, j) \\ =& \sum_{d = 1}^n \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} d \times id \times jd \times [\gcd(i, j) = 1] \\ =& \sum_{d = 1}^n d^3 \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} ij \sum_{k | i, k | j} \mu(k) \\ =& \sum_{d = 1}^n d^3 \sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(k) \sum_{i = 1}^{\lfloor \frac{n}{dk} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{dk} \rfloor} ijk^2 \\ =& \sum_{d = 1}^n d^3 \sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(k) k^2 S(\lfloor \dfrac{n}{dk} \rfloor)^2 \end{align} \]求：
\[\sum_{i = 1}^n \sum_{j = 1}^n ij \gcd(i, j) \pmod{p} \]\(n \leq 10^{10}\)
其中 \(S(n) = \dfrac{n(n + 1)}{2}\) ，令 \(T = dk\) 则：
\[\begin{align} =& \sum_{T = 1}^n T^2 S(\lfloor \dfrac{n}{T} \rfloor)^2 \sum_{d | T} d \mu(\dfrac{T}{d}) \\ =& \sum_{T = 1}^n S(\lfloor \dfrac{n}{T} \rfloor)^2 T^2 \varphi(T) \end{align} \]杜教筛处理 \(T^2 \varphi(T)\) 的前缀和即可，具体为构造 \(g(n) = n^2\) 。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e7 + 7;
map<ll, int> mp;
int pri[N], phi[N], sum[N];
bool isp[N];
ll n;
int Mod, pcnt, inv6;
inline int add(int x, int y) {
x += y;
if (x >= Mod)
x -= Mod;
return x;
}
inline int dec(int x, int y) {
x -= y;
if (x < 0)
x += Mod;
return x;
}
inline int mi(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % Mod)
if (b & 1)
res = 1ll * res * a % Mod;
return res;
}
inline void sieve() {
memset(isp, true, sizeof(isp));
isp[1] = false, phi[1] = 1;
for (int i = 2; i < N; ++i) {
if (isp[i])
pri[++pcnt] = i, phi[i] = i - 1;
for (int j = 1; j <= pcnt && i * pri[j] < N; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
phi[i * pri[j]] = phi[i] * phi[pri[j]];
else {
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
for (int i = 1; i < N; ++i)
sum[i] = add(sum[i - 1], 1ll * i * i % Mod * phi[i] % Mod);
}
inline int Sum1(ll n) {
n %= Mod;
return n * (n + 1) / 2 % Mod;
}
inline int Sum2(ll n) {
n %= Mod;
return n * (n + 1) % Mod * (n * 2 + 1) % Mod * inv6 % Mod;
}
int Sum(ll n) {
if (n < N)
return sum[n];
if (mp.find(n) != mp.end())
return mp[n];
int res = 1ll * Sum1(n) * Sum1(n) % Mod;
for (ll l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res = dec(res, 1ll * dec(Sum2(r), Sum2(l - 1)) * Sum(n / l) % Mod);
}
return mp[n] = res;
}
signed main() {
scanf("%d%lld", &Mod, &n);
sieve();
inv6 = mi(6, Mod - 2);
int ans = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = add(ans, 1ll * Sum1(n / l) * Sum1(n / l) % Mod * dec(Sum(r), Sum(l - 1)) % Mod);
}
printf("%d", ans);
return 0;
}
求：
\[\sum_{i_1 = L}^R \sum_{i_2 = L}^R \cdots \sum_{i_n = L}^R [\gcd(i_1, i_2, \cdots, i_n) = k] \pmod{10^9 + 7} \]\(n, k \leq 10^9\) ，\(L, R \leq 10^9\) ，\(R - L \leq 10^5\)
令 \(l = \lceil \dfrac{L}{k} \rceil, r = \lfloor \dfrac{R}{k} \rfloor\) ，则：
\[\begin{align} & \sum_{i_1 = L}^R \sum_{i_2 = L}^R \cdots \sum_{i_n = L}^R [\gcd(i_1, i_2, \cdots, i_n) = k] \\ =& \sum_{i_1 = l}^r \sum_{i_2 = l}^r \cdots \sum_{i_n = l}^r [\gcd(i_1, i_2, \cdots, i_n) = 1] \\ =& \sum_{i_1 = l}^r \sum_{i_2 = l}^r \cdots \sum_{i_n = l}^r \sum_{d | i_1, d | i_2, \cdots, d | i_n} \mu(d) \\ =& \sum_{d = 1}^r \mu(d) (\lfloor \dfrac{r}{d} \rfloor - \lfloor \dfrac{l - 1}{d} \rfloor)^n \end{align} \]#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const int N = 1e7 + 7;
map<int, int> mp;
int pri[N], mu[N], sum[N];
bool isp[N];
int n, k, L, R, pcnt;
inline int add(int x, int y) {
x += y;
if (x >= Mod)
x -= Mod;
return x;
}
inline int dec(int x, int y) {
x -= y;
if (x < 0)
x += Mod;
return x;
}
inline int mi(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = 1ll * a * a % Mod)
if (b & 1)
res = 1ll * res * a % Mod;
return res;
}
inline void sieve() {
memset(isp, true, sizeof(isp));
isp[1] = false, mu[1] = 1;
for (int i = 2; i < N; ++i) {
if (isp[i])
pri[++pcnt] = i, mu[i] = Mod - 1;
for (int j = 1; j <= pcnt && i * pri[j] < N; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
mu[i * pri[j]] = Mod - mu[i];
else {
mu[i * pri[j]] = 0;
break;
}
}
}
for (int i = 1; i < N; ++i)
sum[i] = add(sum[i - 1], mu[i]);
}
inline int Sum(int n) {
if (n < N)
return sum[n];
if (mp.find(n) != mp.end())
return mp[n];
int res = 1;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res = dec(res, 1ll * (r - l + 1) * Sum(n / l) % Mod);
}
return mp[n] = res;
}
signed main() {
sieve();
scanf("%d%d%d%d", &n, &k, &L, &R);
L = (L - 1) / k, R /= k;
int ans = 0;
for (int l = 1, r; l <= R; l = r + 1) {
r = R / (R / l);
if (L / l)
r = min(r, L / (L / l));
ans = add(ans, 1ll * mi(R / l - L / l, n) * dec(Sum(r), Sum(l - 1)) % Mod);
}
printf("%d", ans);
return 0;
}