题意
给定 \(n, k\)，对于所有的 \(m \in \left[1, k\right]\)，求长度为 \(n\)，值域为 \(\left[1,m \right]\) 且最大公约数为 \(1\) 的序列种数，对 \(10^9 + 7\) 取模。
（\(1 \le n,k \le 2 \times 10^6\)）。
题解
设 \(f(d, m)\) 表示长度为 \(n\)，值域为 \(\left[1,m \right]\) 且最大公约数为 \(1\) 的序列种数，\(g(d, m)\) 表示长度为 \(n\)，值域为 \(\left[1,m \right]\) 且序列元素均为 \(d\) 的倍数即最大公约数为 \(d\) 的倍数的序列种数，那么有
考虑计算 \(g(d, m)\)，发现
综上，可得
现在我们得到了答案的计算式，但是若对于每个 \(m\) 应用整除分块计算，复杂度为 \(\mathcal{O}(k \sqrt{k} \log n)\)，若使用线性筛预处理出幂函数，那么复杂度为 \(\mathcal{O}(k \sqrt{k})\)，均无法通过本题。
故考虑在 \(f(1, m - 1)\) 的基础上计算 \(f(1, m)\)，考虑 \(f(1, m)\) 较 \(f(1, m - 1)\) 的差值均为 \(\left\lfloor\dfrac{m}{i}\right\rfloor\) 的改变引起的，而对于每个 \(i\)，只有 \(m\) 增大为 \(i\) 的倍数时该值才会改变，故答案共会改变 \(\mathcal{O}(k \ln k)\) 次。形式化的，有
而 \(\left\lfloor\dfrac{m}{i}\right\rfloor^n - \left(\left\lfloor\dfrac{m}{i}\right\rfloor - 1\right)^n\) 的取值只有 \(i \mid m\) 时才不为 \(0\)，故上式后半部分在 \(m\) 取遍 \(\left[1, k\right]\) 时产生贡献的次数共为 \(\mathcal{O}(k \ln k)\) 次。
对于每个数，预处理其因子，在 \(m\) 增长后，对于当前 \(m\) 的所有因子 \(i\)，\(\left\lfloor\dfrac{m}{i}\right\rfloor\) 的值均会增长 \(1\)，将答案累加 \(\mu\left(i\right)\times\left(\left\lfloor\dfrac{m}{i}\right\rfloor^n - \left(\left\lfloor\dfrac{m}{i}\right\rfloor - 1\right)^n\right)\) 即可。
使用线性筛预处理出幂函数即可，在 \(n,k\) 同阶的情况下，总复杂度为 \(\mathcal{O}(n \log n)\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;
constexpr valueType MOD = 1e9 + 7;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
class LineSieve {
public:
typedef std::vector<valueType> container;
private:
valueType N, M;
container prime;
bitset isPrime;
container Mobius, Power;
ValueMatrix Factor;
public:
LineSieve(valueType n, valueType m) : N(n), M(m), prime(), isPrime(n + 1, true), Mobius(n + 1, 1), Factor(n + 1),
Power(n + 1, 1) {
isPrime[0] = isPrime[1] = false;
Mobius[1] = 1;
Power[1] = 1;
for (valueType i = 2; i <= N; ++i) {
if (isPrime[i]) {
prime.push_back(i);
Mobius[i] = -1;
Power[i] = ::pow(i, M);
}
for (auto const &iter: prime) {
valueType const t = i * iter;
if (t > N)
break;
isPrime[t] = false;
Power[t] = mul(Power[i], Power[iter]);
if (i % iter == 0) {
Mobius[t] = 0;
break;
} else {
Mobius[t] = -Mobius[i];
}
}
if (Mobius[i] < 0)
Mobius[i] += MOD;
}
for (valueType i = 1; i <= N; ++i)
for (valueType j = i; j <= N; j += i)
Factor[j].push_back(i);
}
valueType operator()(valueType n) const {
return Mobius[n];
}
valueType pow(valueType n) const {
return Power[n];
}
const ValueVector &fact(valueType n) const {
return Factor[n];
}
};
int main() {
valueType N, K;
std::cin >> N >> K;
LineSieve const sieve(K, N);
ValueVector ans(K + 1, 0), F(K + 1, 0);
for (valueType i = 1; i <= K; ++i) {
ans[i] = ans[i - 1];
for (auto const &iter: sieve.fact(i)) {
Inc(ans[i], mul(sieve(iter), sub(sieve.pow(i / iter), sieve.pow(i / iter - 1))));
Inc(F[i / iter], sub(sieve.pow(i / iter), sieve.pow(i / iter - 1)));
}
F[i] = sieve(i);
Inc(ans[i], F[i]);
}
valueType result = 0;
for (valueType i = 1; i <= K; ++i)
Inc(result, ans[i] ^ i);
std::cout << result << std::endl;
}