Codeforces 900D. Unusual Sequences

Count the number of distinct sequences a1, a2, …, an (1 ≤ ai) consisting of positive integers such that gcd(a1, a2, …, an) = x and . As this number could be large, print the answer modulo 109 + 7.

gcd here means the greatest common divisor.

Input

The only line contains two positive integers x and y (1 ≤ x, y ≤ 109).

Output

Print the number of such sequences modulo 109 + 7.

Examples

Note

There are three suitable sequences in the first test: (3, 3, 3)(3, 6)(6, 3).

There are no suitable sequences in the second test.

题意简述

给出两个整数 x、y,求有多少个长度不限的数列,满足数列的最大公因数是 x 且数列的和为 y。

分析

首先,数列的最大公因数是 x,就说明所有数都是 x 的倍数,那么 y 也必然是 x 的倍数。

然后将所有数除以 x,得到的数列的最大公因数就是 1,而和就变成了 $\frac{y}{x}$。

那么问题就转化为了,求最大公因数为 1,和为 n 的数列的个数。

求最大公因数是 1 的数列个数不好求,但是最大公因数是 1 的倍数的数列个数就比较好求了,根据隔板法可以知道长度为 i 的数列个数为 ${n-1}\choose{i-1}$。求个和,数列的总个数就是 $2^{n-1}$。

用同样的方法还可以求出最大公因数是 x 的倍数的数列个数,将数列都除以 x,得到的数列的和就是 $\frac{n}{x}$,方案数就是 $2^{\frac{n}{x}-1}$。

求出来之后想办法利用容斥原理求最大公因数刚好是 1 的数列方案数,实际上这个东西叫做莫比乌斯反演(这个地方一开始看很久没看出来,大概是废了)。

用筛法求莫比乌斯函数只要预处理超过 $\sqrt{\frac{y}{x}}$ 即可,超过根号部分可以通过分解质因数求解。

 

发表评论