我们知道，从区间 [L,H]（L 和 H 为整数）中选取 N 个整数，总共有 (H−L+1)N 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 N 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 K，你需要回答他最大公约数刚好为 K 的选取方案有多少个。由于方案数较大，你只需要输出其除以 109+7 的余数即可。
输入一行，包含四个空格分开的正整数，依次为 N,K,L,H。
输出一个整数，为所求方案数。
首先，进行如下处理：
1、如果L是K的倍数，那么把L变为KL，否则变为⌊KL⌋+1。
2、把H变成⌊KH⌋。
这样子容易得出，现在要求的就是在[L,H]之间，选数N次使选出的数最大公约数为1的方案数。
现在，用fi表示选出的数的最大公约数i且选出的数不全相同的方案数。此时先求出[L,H]之间i的倍数的个数x，暂时令fi=xN−x。
但此时得到的fi实际上是含有公约数i的方案数，不是最大公约数为i的方案数。但是可以发现，此时的fi包含有最大公约数为i,2i,3i,…的方案数。这时候使用容斥原理：假设已经知道了f2i,f3i,…的最终结果，那么就把fi分别减去f2i,f3i,…，就可以得到fi的最终结果。倒着推一遍。
特殊情况：L=1时可以所有的数都选1。所以L=1时答案要加1。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
#include "ybwhead/ios.h"
using namespace std;
const int mod = 1e9 + 7;
int n, k, l, h;
long long ksm(long long a, int n)
{
if (n == 1)
return a;
if (n == 0)
return 1;
long long ans = ksm(a, n >> 1);
ans = ans * ans % mod;
if (n & 1)
ans = a * ans % mod;
return ans;
}
const int maxn = 1e5 + 7;
int f[maxn];
int main()
{
yin >> n >> k >> l >> h;
l = (l + k - 1) / k;
h /= k;
if (l > h)
{
puts("0");
return 0;
}
for (int i = 1; i <= h - l; i++)
{
int L = l, r = h;
if (L % i)
L = L / i + 1;
else
L /= i;
r /= i;
if (L > r)
continue;
f[i] = (ksm(r - L + 1, n) - (r - L + 1) + mod) % mod;
}
for (int i = h - l; i; i--)
for (int j = (i << 1); j <= h - l; j += i)
f[i] = (f[i] - f[j] + mod) % mod;
if (l == 1)
(f[1] += 1) %= mod;
cout << f[1] << endl;
return 0;
}
|
v1.4.14