自动搬运

查看原文

来自洛谷，原作者为

	dovely_seele 对不起。

搬运于2025-08-24 21:50:35，当前版本为作者最后更新于2023-07-15 01:55:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能我阅读理解能力不太好，没看懂其他题解（

首先根据等比数列求和公式 $f(n)$ 显然等于 $\frac{x^{n+1}-1}{x-1}$，分母 $x-1$ 是个定值可以直接先扔出来。所以就是让你求一堆形如 $x^a-1$ 的数的最小公倍数。

首先考虑只有两个数的情况，这时 lcm 也就是乘积除以 gcd。 根据具体数学习题 4.38，$gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$。书上是用辗转相除证的，其实不用也可以。

首先显然 $x^{gcd(a,b)}-1$ 是两数的公约数（参考具体数学习题 4.22），然后只需要证明它是最大的即可。接下来的一步比较有意思：找两个正整数 $n, m$ 使得 $na=mb+gcd(a,b)$（根据 exgcd，肯定能找到这两个数），那么 $gcd(x^a-1,x^b-1)|x^b-1|x^{mb}-1$，所以 $gcd(x^a-1,x^b-1)|x^{gcd(a,b)}(x^{mb}-1)$，而后者展开之后就是 $x^{mb+gcd(a,b)}-x^{gcd(a,b)}=x^{na}-x^{gcd(a,b)}$，由于已知 $x^{na}$ 除以 $gcd(x^a-1,x^b-1)$ 的余数是 $1$，所以 $x^{gcd(a,b)}$ 除以 $gcd(x^a-1,x^b-1)$ 的余数也是 1，也就是说 $gcd(x^a-1,x^b-1)|x^{gcd(a,b)}-1$，所以它一定是最大的。

现在如果换成多个数如何求 lcm 呢？两个数取 lcm 之后已经不是 $x^a-1$ 的形式，无法再套用前面的结论。手玩一下 $n=3$ 和 $n=4$ 的情况可以发现一个集合的 lcm 就是所有大小为奇数的子集的 gcd 乘积除以所有大小为偶数的子集的 gcd 乘积。（这很好理解，因为求 gcd 本质上就是求两个约数集合的交。）

我们用 map 维护一个集合中所有子集中每个 gcd 的出现次数（由于 gcd 也是 $x^a-1$ 的形式，只需要记录指数即可），由于这些 gcd 显然至少是其中一个数的约数，所以集合最多也只有 $O(n\sqrt{V})$ 个元素。然后每次加入一个元素，这时新的集合的所有子集可以分为两类：包含新元素和不包含新元素的，后者 gcd 的乘积就是原来集合的 lcm，前者就是把原来集合的每一个子集 gcd 和新的数取 gcd 后取倒数（因为集合的大小奇偶性反转了），遍历一遍 map 算完了再将两者加起来即可。粗略估算一下，时间复杂度算上 map 的一个 log 是 $O(n^2\sqrt{V}logn)$，而且严重不满，可以通过。（输出答案的时候不要忘记乘以一开始丢掉的 $x-1$ 的逆元）

说的不太清楚，看代码吧。

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<long long, long long> s, seele;
long long qp(long long n, long long m, long long p) {
    long long ans = 1, base = n;
    while (m) {
        if (m & 1) (ans *= base) %= p;
        (base *= base) %= p; m >>= 1;
    }
    return ans;
}
int main() {
long long x, n, t, prod=1; cin>> x>> n; x %= (long long)(1e9+7); for (int i=1; i<=n; i++) {
cin>> t; ++t; seele.clear(); for (auto it: s) seele[it.first] = it.second; for (auto it : seele) s[__gcd(it.first, t)] -= it.second; s[t]++;
} for (auto it: s) (prod *= it.second> 0?qp(qp(x, it.first, 1e9+7) - 1, it.second, 1e9+7): qp(qp(qp(x, it.first, 1e9+7) - 1, -it.second, 1e9+7), 1e9+5, 1e9+7)) %= (long long)(1e9+7); cout << prod * qp(x-1, 1e9+5, 1e9+7) % (long long)(1e9+7);
}