P3172-[CQOI2015]选数
题目:
题目描述:
我们知道，从区间 $[L,H]$（$L$ 和 $H$ 为整数）中选取 $N$ 个整数，总共有 $(H-L+1)^N$ 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 $N$ 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 $K$，你需要回答他最大公约数刚好为 $K$ 的选取方案有多少个。由于方案数较大，你只需要输出其除以 $10^9+7$ 的余数即可。
输入格式:
输入一行，包含四个空格分开的正整数，依次为 $N,K,L,H$。
输出格式:
输出一个整数，为所求方案数。
样例:
样例输入 1:
样例输出 1:
思路:
首先，进行如下处理：
1、如果$L$是$K$的倍数，那么把$L$变为$\frac{L}{K}$，否则变为$\lfloor\frac{L}{K}\rfloor+1$。
2、把$H$变成$\lfloor\frac{H}{K}\rfloor$。
这样子容易得出，现在要求的就是在$[L,H]$之间，选数$N$次使选出的数最大公约数为$1$的方案数。
现在，用$f_i$表示选出的数的最大公约数$i$且选出的数不全相同的方案数。此时先求出$[L,H]$之间$i$的倍数的个数$x$，暂时令$f_i=x^N-x$。
但此时得到的$f_i$实际上是含有公约数$i$的方案数，不是最大公约数为$i$的方案数。但是可以发现，此时的$f_i$包含有最大公约数为$i,2i,3i,…$的方案数。这时候使用容斥原理：假设已经知道了$f_{2i},f_{3i},…$的最终结果，那么就把$f_i$分别减去$f_{2i},f_{3i},…$，就可以得到$f_i$的最终结果。倒着推一遍。
特殊情况：$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;
}
|