Sotution to CF258C Little Elephant and LCM。
0#：那么这个 pn 可以等于什么？它只能等于 pm。（露出看到 plmm 一般的猥琐坏笑）
方便起见，下面 \(b_{\text{lcm}}\) 的意思就是 \(\text{lcm}\{b_1,b_2,\cdots,b_n\}\)，\(\max\) 什么的也同理。
首先我们都能反应过来，如果 \(b_{\text{lcm}}=b_{\max}\)，那么 \(b\) 中的最大值就得是 \(b_{\text {lcm}}\)，而其他元素都得是 \(b_{\max}\) 的因数。
既然涉及到求 \(b_{\max}\) 的因数，那我们势必避免不了枚举 \(b_{\max}\)。我一开始陷入了一个 trick：我并不知道 \(b_{\max}\) 应该处于哪一个位置。但其实这不重要，它对我们最后的方案没有影响，有影响的是「有多少个位置可以取到当前枚举的 \(b_{\max}\)」。
对于当前枚举的 \(b_{\max}\)（假设为 \(k\)），我们找到它的所有因数 \(p_1\sim p_m\)，按从小到大的顺序排列。对于一个 \(a_i\)，当且仅当 \(a_i\ge p_j\) 时，\(a_i\) 可以选择 \(p_j\)。那么我们找到 \(a_i\) 可以选到的最大的 \(p_j\)，此时 \(a_i\) 的选择就是 \(p_1\sim p_j\)，共 \(j\) 种。
那么我们在外面已经有一层枚举 \(k\) 的循环的前提下，再遍历 \(a\) 数组无疑是会起飞的，我们考虑倒过来，遍历 \(p\)，对于每个 \(p_j\)，找到它是多少个 \(a_i\) 的最大选择（假设为 \(x_j\)），那么对于 \(p_j\)，它贡献的答案就是 \(j^{x_j}\)。
\(x_j\) 的计算也不难，我们用两个二分找到满足 \(p_j\le a_i < p_j + 1\) 的 \(a_i\) 数量就可以了。那么总方案数就是 \(\prod j^{x_j}\)。
但是别忘了还有 \(k\) 为 \(b_{\max}\) 的限制。找到 \(x_m\)，怎么去满足至少有一个 \(a_i=k\) 呢？一个微型容斥，用总方案数减去一个 \(k\) 都没有的方案数。那么就规定了每个可以取到 \(k\) 的数都必须不取 \(k\)，本来有 \(m\) 种选择，现在只剩下 \(m−1\) 种，所以答案就是 \((m−1)^{x_m}\)，容斥后为 \(m^{x_m}−(m−1)^{x_m}\)。
对于 \(b_{\max}=k\)，最终结果为 \((\prod\limits_{j=1}^{m−1}j^{x_j})\times (m^{x_m}−(m−1)^{x_m})\)。加法原理把所有 \(k\) 的情况加起来即可。
对于时间复杂度，枚举 \(k\) 是 \(O(V)\) 的，找因数是 \(O(\sqrt V)\) 的，枚举 \(p_j\) 是 \(\log V\) 的，二分是 \(\log n\) 的。所以最终时间复杂度为 \(O(V\times \max\{\sqrt V,\log V\times \log n\})\)。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int a[maxn];
int n, mx, ans, res;
int qkp(int x, int y) {
int res = 1;
while (y) {
if (y & 1) (res *= x) %= mod;
(x *= x) %= mod, y >>= 1;
}
return res;
}
int max(int x, int y) { return x > y ? x : y; }
int main() {
read(n);
for (int i = 1; i <= n; ++i)
read(a[i]), mx = max(mx, a[i]);
std::sort(a + 1, a + n + 1);
for (int k = 1; k <= mx; ++k) {
res = 1;
std::vector<int> p;
p.push_back(-1); // 占位符，方便下标对齐
for (int i = 1; i * i <= k; ++i) {
if (k % i == 0) {
p.push_back(i);
if (i * i != k) p.push_back(k / i);
}
}
std::sort(p.begin() + 1, p.end());
// 先算前 m - 1 个
int m = p.size() - 1;
for (int j = 1; j <= m - 1; ++j) {
int l, r, x;
l = std::lower_bound(a + 1, a + n + 1, p[j]) - a;
r = std::lower_bound(a + 1, a + n + 1, p[j + 1]) - a - 1;
x = r - l + 1, (res *= qkp(j, x)) %= mod;
}
int l, r, x;
l = std::lower_bound(a + 1, a + n + 1, p[m]) - a;
r = n, x = r - l + 1;
(res *= (qkp(m, x) - qkp(m - 1, x))) %= mod;
(ans += res) %= mod;
}
print((ans + mod) % mod, '\n');
return 0;
}
} // namespace XSC062
#undef int