多少岁月想要伴你走过 燕回春野蝉鸣夏夜说予我

· · 题解

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

首先根据等比数列求和公式 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);
}