[CQOI 2015]选数

Description

我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个整数K，你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大，你只需要输出其除以1000000007的余数即可。

Input

输入一行，包含4个空格分开的正整数，依次为N，K，L和H。

Output

输出一个整数，为所求方案数。

Sample Input

2 2 2 4

Sample Output

HINT

样例解释

所有可能的选择方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)

其中最大公约数等于2的只有3组：(2, 2), (2, 4), (4, 2)

对于100%的数据，1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5

题解

设 $F(x)$ 为 $x\mid gcd$ 的个数， $f(x)$ 为 $gcd=x$ 的个数。

\begin{aligned}F(x)&=\sum_{x\mid d}f(d)\\\Rightarrow f(x)&=\sum_{x\mid d}\mu\left(\frac{d}{x}\right)F(d)\end{aligned}

对于输入 $(N,K,L,H)$ 我们记 $\left\lceil\frac{L}{K}\right\rceil$ 为 $l$ ，记 $\left\lfloor\frac{H}{K}\right\rfloor$ 为 $h$ 。

提出 $K$ ，答案就是 $$f(1)=\sum_{i=1}^{h}\mu(i)F(i)$$

显然 $F(i)=\left(\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\right)^N$

由于 $h$ 很大，我们还是不能枚举这个 $i$ 。考虑到这样一个问题：当 $i$ 很大时 $\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor$ 会变成 $0$ 或 $1$ 。实际上只要 $i>h-l$ 数值就为 $0$ 或 $1$ 了。

那么现在答案就变成了 \begin{aligned}&\sum_{i=1}^{h-l}\mu(i)\left(\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\right)^N+\sum_{i=h-l+1}^h\mu(i)\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\\=&\sum_{i=1}^{h-l}\mu(i)\left(\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\right)^N+\sum_{i=1}^h\mu(i)\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor-\sum_{i=1}^{h-l}\mu(i)\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\end{aligned}

我们观察到式子 $\sum\limits_{i=1}^h\mu(i)\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor$ 的含义就是 $l\sim r$ 区间内有是否有值为 $1$ ，所以等价于 $[L\leq K\wedge K\leq H]$ 。

所以 $$ans=\sum_{i=1}^{h-l}\mu(i)\left(\left(\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\right)^N-\left(\left\lfloor\frac{h}{i}\right\rfloor-\left\lfloor\frac{l-1}{i}\right\rfloor\right)\right)+[L\leq K\wedge K\leq H]$$

 //It is made by Awson on 2018.1.24

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 #define writeln(x) (write(x), putchar('\n'))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int N = 1e5;

 const int MOD = ;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(LL x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 int n, k, l, h, mu[N+];

 int isprime[N+], prime[N+], tot;

 void get_mu() {

     memset(isprime, , sizeof(isprime)); isprime[] = , mu[] = ;

     for (int i = ; i <= N; i++) {

     if (isprime[i]) prime[++tot] = i, mu[i] = -;

     for (int j = ; j <= tot && i*prime[j] <= N; j++) {

         isprime[i*prime[j]] = ;

         if (i%prime[j]) mu[i*prime[j]] = -mu[i];

         else {mu[i*prime[j]] = ; break; }

     }

     }

 }

 int quick_pow(int a, int b) {

     int ans = ;

     while (b) {

     if (b&) ans = (LL)ans*a%MOD;

     a = (LL)a*a%MOD, b >>= ;

     }

     return ans;

 }

 void work() {

     get_mu(); read(n), read(k), read(l), read(h);

     int flag = (l <= k && k <= h), ans = ;

     l = ceil(.*l/k), h = (h/k);

     for (int i = ; i <= h-l; i++) ans = (ans+(LL)mu[i]*quick_pow(h/i-(l-)/i, n)%MOD)%MOD;

     for (int i = ; i <= h-l; i++) ans = (ans-(LL)mu[i]*(h/i-(l-)/i)%MOD)%MOD;

     writeln((ans+flag+MOD)%MOD);

 }

 int main() {

     work();

     return ;

 }

巴特西