1. 2^x = x
给定素数 $p_1, p_2, \cdots, p_N$，对于每个 $i$ 求出满足 $2^x \equiv x \pmod {p_i}$ 且不超过 $10^{18}$ 的一个正整数解 $x$
限制：
- $1 \leqslant N \leqslant 1000$
- $2 \leqslant p_i \leqslant 10^9$
算法分析
由 费马小定理 可知，当 $\gcd(a, p) = 1$ 时，有 $a^{p-1} \equiv 1 \pmod p$，在同余号两边做 $p-1$ 次乘幂可得 $a^{(p-1)^2} \equiv 1 \pmod p$。
另一方面，$(p-1)^2 = p^2 - 2p + 1 \equiv 1 \pmod p$。
而在本题中 $a = 2$，那么只有当 $p$ 为奇素数时，$x$ 可以是 $(p-1)^2$；当 $p=2$ 时，特判一下即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using ll = long long;
int main() {
int n;
cin >> n;
rep(i, n) {
ll p;
cin >> p;
if (p == 2) puts("2");
else cout << (p - 1) * (p - 1) << '\n';
}
return 0;
}
2. N的连续数拆分
所有的正整数均可以表示为一个、两个或者多个连续正整数的和。
给定一个不超过 $9\times 10^{14}$ 的正整数，求出它可以用几种不同的方法表示成连续正整数之和。例如给出 $9$，则有三种方式：$9,4+5,2+3+49,4+5,2+3+4$
算法分析
$ n = \sum\limits_{k=l}^r k = \frac{(l+k)(r-k+1)}{2} \Rightarrow (l+r)(r-l+1) = 2n $
注意到 $l+r$ 和 $r-l$ 的奇偶性一样，所以 $l+r$ 和 $r-l+1$ 的奇偶性恰好相反
所以我们只需暴力枚举较小的因子 $r-l+1$ 即可，时间复杂度可做到 $O(\sqrt{2n})$
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
int main() {
ll n;
cin >> n;
n *= 2;
int ans = 0;
for (ll x = 1; x*x <= n; ++x) {
if (n % x != 0) continue;
int y = n/x;
ans += x%2 != y%2;
}
cout << ans << '\n';
return 0;
}
3. It’s About Drive
假设你正在开车。令你的车速为 $v$，这意味着你将以每秒行驶 $v$ 米。一开始，$v = 0$。
在每秒钟（包含第 $0$ 秒）开始时，你可以执行以下任意操作之一：
- 将 $v$ 增加 $1$
- 若 $v > 0$，将 $v$ 减 $1$
- 保持 $v$ 不变
在 $N$ 秒之后，你恰行驶了 $D$ 米。你最后的车速 $v$ 也必须等于 $F$。判断是否可以做到。
限制：
- $1 \leqslant N, F \leqslant 1000000$
- $1 \leqslant D \leqslant 10^{18}$
算法分析
我们可以按如下方式定义序列 $A$:
- 对于每个 $i \ (1 \leqslant i \leqslant N)$，$A_i$ 为第 $i$ 秒 $v$ 的值，且 $A_0 = 0$
由题意可知，$\forall \ i \ (1 \leqslant i \leqslant N)$，$|A_i - A_{i-1}| \leqslant 1$。由此可以推出 $A_N \leqslant N$，所以需要 $F \leqslant N$
由于 $A_N = F$，于是我们可以得到
- $A_{N-1} \geqslant F-1$
- $A_{N-2} \geqslant F-2$
- $\vdots$
- $A_{N-F} \geqslant 0$
所以你可以行驶的最小距离为 $\sum\limits_{i=0}^F i = \frac{(F+1)F}{2}$
运用同样的逻辑，由于 $A_0 = 0$，于是
- $A_1 \leqslant 1$
- $A_2 \leqslant 2$
- $\vdots$
- $A_i \leqslant i$
而 $A_N = F$，我们也可以得到
- $A_N \leqslant F$
- $A_{N-1} \leqslant F-1$
- $\vdots$
- $A_i \leqslant F + N - i$
所以你可以行驶的最大距离就是 $\sum\limits_{i=1}^N \min(i, F+N-i)$
最后，我们只需判断 $D$ 是否介于最小距离和最大距离之间即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using std::cin;
using std::cout;
using std::min;
using ll = long long;
int main() {
int n, f;
ll d;
scanf("%d%d%ld", &n, &f, &d);
if (f > n) {
puts("NO");
return 0;
}
ll min_d = (ll)(f+1) * f / 2;
ll max_d = 0;
rep(i, n) max_d += min(i, f+n-i);
puts(min_d <= d and d <= max_d ? "YES" : "NO");
return 0;
}
4. OMC65B
有多少对不同的正整数三元组满足 $abc=360$，其中 $(a, b, c)$ 是有序的
分析：
结论：
不定方程 $x_1 + x_2 + \cdots + x_m = n (n, m \in {\mathbb{N}}^{+})$ 的非负整数解 $(x_1, x_2, \cdots, x_m)$ 的个数为 $\binom{n+m-1}{m-1}$
$360 = 2^3 \times 3^2 \times 5$
若不考虑 $a, b, c$ 不同的话，则方案数可以通过求出
$x+y+z = 3$ 或 $x+y+z = 2$ 或 $x+y+z = 1$
的非负整数解 $(x, y, z)$ 的个数求出，由上面的结论可知 $\binom{3+3-1}{3-1} \binom{2+3-1}{3-1} \binom{1+3-1}{3-1} = \binom{5}{2} \binom{4}{2} \binom{3}{2} = 180$
再考虑到 $1, 2, 3, 6$ 可能会出现在两个位置上，所以最后的答案为 $180 - 4 \times 3 = 168$
5. Exponentiation II
求 $a^{b^c}$，并对其模 $10^9 + 7$
要求多组数据询问
限制：
- $1 \leqslant t \leqslant 10^5$
- $0 \leqslant a, b, c \leqslant 10^9$
算法分析
对于正整数 $n$ 与正整数 $a$，$\rm{Euler}$ 定理说明如果 $a \perp b$，那么对于任意的 $m$，有
$$ a^m \equiv a^{m \bmod \varphi(n)} \pmod n $$
如果 $a \not\perp n$，若 $m \geqslant \varphi(n)$，我们有以下结论：
$$ a^m \equiv a^{m \bmod \varphi(n) + \varphi(n)} \pmod n $$
由费马小定理可知，$a^{p-1} \equiv 1 \pmod p$
$$ \begin{aligned} a^{b^c} = (a)^{b^c} &\equiv a^{{(b^c)} \bmod (p-1) + (p-1)} \pmod p \equiv a^{{(b^c)} \bmod (p-1)} \cdot a^{p-1} \pmod p \\\ &\equiv a^{{(b^c)} \bmod (p-1)} \cdot 1 \pmod p \equiv a^{{(b^c)} \bmod (p-1)} \pmod p \end{aligned} $$
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
const int mod = 1000000007;
ll pow_mod(ll a, ll k, int p) {
ll res = 1;
while (k) {
if (k&1) res = res*a%p;
a = a*a%p;
k >>= 1;
}
return res;
}
void solve() {
ll a, b, c;
cin >> a >> b >> c;
ll x = pow_mod(b, c, mod-1);
ll ans = pow_mod(a, x, mod);
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
6. Common Divisors
给你一个包含 $n$ 个正整数的数组，要求你找出这个数组中任意两个数的最大 $\gcd$
限制：
- $1 \leqslant n \leqslant 10^5$
- $1 \leqslant x_i \leqslant 10^6$
算法分析
可以从大到小遍历所有可能的 $\gcd$，统计数组中有多少数可以被这个 $\gcd$ 整除，如果该数量 $\geqslant 2$，直接输出即可
时间复杂度：$O(\max(x_i)\log (\max(x_i)))$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::unordered_map;
const int MX = 1000001;
int main() {
int n;
cin >> n;
unordered_map<int, int> freq;
rep(i, n) {
int x;
cin >> x;
freq[x]++;
}
for (int g = MX-1; g > 0; --g) {
int div = 0;
for (int j = g; j < MX; j += g) {
div += freq[j];
}
if (div >= 2) {
cout << g << '\n';
break;
}
}
return 0;
}
7. Fibonacci Numbers
斐波那契数的定义如下：
- $F_0 = 0$
- $F_1 = 1$
- $F_n = F_{n-2} + F_{n-1}$
要求对于给定的整数 $n$，求出 $F_n$ 的值并对 $10^9+7$ 取模
限制：
- $0 \leqslant n \leqslant 10^{18}$
算法分析
$ \begin{bmatrix} 1 & 1\\\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\\ F_{n-2} \end{bmatrix} = \begin{bmatrix} F_n\\\ F_{n-1} \end{bmatrix} $
我们只要计算这个转移矩阵 $\begin{bmatrix} 1 & 1\\\ 1 & 0 \end{bmatrix}$ 的 $n-1$ 次幂就可以了。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
const int mod = 1000000007;
vector<vector<ll>> matmul(vector<vector<ll>> A, vector<vector<ll>> B) {
int n = A.size();
vector<vector<ll>> C(n, vector<ll>(n));
rep(i, n)rep(j, n)rep(k, n) {
C[i][k] += A[i][j] * B[j][k];
C[i][k] %= mod;
}
return C;
}
vector<vector<ll>> matexp(vector<vector<ll>> A, ll b) {
int n = A.size();
vector<vector<ll>> Z(n, vector<ll>(n));
rep(i, n) Z[i][i] = 1;
while (b > 0) {
if (b & 1) Z = matmul(Z, A);
A = matmul(A, A);
b /= 2;
}
return Z;
}
int main() {
ll n;
cin >> n;
if (n == 0) puts("0");
else if (n == 1) puts("1");
else {
vector A(2, vector<ll>(2));
A[0][0] = A[0][1] = A[1][0] = 1;
A = matexp(A, n-1);
cout << A[0][0] << '\n';
}
return 0;
}
8. Counting Sequences
统计含有 $n$ 个整数且满足以下条件的序列 $a$ 的个数：
- $a_i$ 为 $[1, k]$ 之间的整数
- $[1, k]$ 之中的每个整数在 $a$ 中至少出现一次
并对答案模 $10^9 + 7$
限制：
- $1 \leqslant k \leqslant n \leqslant 10^6$
算法分析
逐步淘汰原理：
设 $A_1, A_2, \cdots, A_n$ 是集合 $S$ 的 $n$ 个子集，则
$ \begin{aligned} |\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}| = |S|-\sum_{i=1}^{n}|A_i|+\sum_{1\leqslant i < j \leqslant n}|A_i \cap A_j|+\cdots + (-1)^k |A_1 \cap A_2 \cap \cdots \cap A_n| \end{aligned} $
本题等价于问 “将 $n$ 个不同的球放入 $k$ 个不同的盒子使得没有盒子为空的方案数”
容易想到，如果去掉没有空的条件，由乘法原理，最终的答案为 $k^n$。但如果出现空盒子呢？
可以指定第 $a_1, a_2, \cdots， a_i$ 个盒子为空，则这 $n$ 个球可以放入剩下的 $k - i$ 个盒子。由乘法原理，在这种情况下有 $(k-i)^n$ 种方案。另外，对于任意 $i$，都有 $_kC_i$ 个满足条件的 $a_1, a_2, \cdots, a_i$，于是可以得出 $i$ 个盒子为空的方案数为 $_kC_i \cdot (k-i)^n$ 。
由容斥原理，可以得到答案为 $\sum_{i=0}^{k-1} (-1)^i _kC_i \cdot (k-i)^n$ 。
双倍经验： 斯特林数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::istream;
using std::ostream;
using std::vector;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
// combination mod prime
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
} comb(1000005);
mint pow_mod(mint a, int b) {
mint res = 1;
while (b) {
if (b&1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
int main() {
int n, k;
cin >> n >> k;
mint ans;
rep(i, k) {
ans += mint(i % 2 == 0 ? 1 : -1) * comb(k, i) * pow_mod(k-i, n);
}
cout << ans << '\n';
return 0;
}
9. Prime Multiples
给你 $k$ 个不同的素数 $a_1, a_2, \cdots, a_k$ 和整数 $n$
统计 $1 \sim n$ 中能被给定的素数中的至少一个整除的数有多少个
限制：
- $1 \leqslant n \leqslant 10^{18}$
- $1 \leqslant k \leqslant 20$
- $2 \leqslant a_i \leqslant n$
算法分析
容斥原理
双倍经验：能被整除的数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
ll n; int m;
cin >> n >> m;
vector<ll> p(m);
rep(i, m) cin >> p[i];
ll ans = 0;
for (int i = 1; i < 1<<m; ++i) {
ll t = 1;
rep(j, m) if (i>>j&1) {
if ((__int128_t)t*p[j] > n) {
t = -1;
break;
}
t *= p[j];
}
if (t != -1) {
if (__builtin_parity(i)) ans += n/t;
else ans -= n/t;
}
}
cout << ans << '\n';
return 0;
}
10. OMC109C
在 $6$ 位数 $(100000 \sim 999999)$ 中等概率地选择一个数，要求满足它不能被 $3$ 整除，但能被 $7$，$11$，$13$ 整除的概率。
分析：
$7, 11, 13$ 的最小公倍数是 $1001$，条件相当于
- 前 $3$ 位和后 $3$ 位相同，但不能被 $3$ 整除
$3$ 位正整数不能被 $3$ 整除的概率是 $\frac{2}{3}$，固定前 $3$ 位后 $3$ 位满足条件的概率是 $\frac{1}{1000}$
所以答案是 $\frac{2}{3} \times \frac{1}{1000} = \frac{1}{1500}$
11. 玩游戏
定义一个数 $x$ 的价值为：将这个数分解成若干个正整数 $a_1, a_2, \cdots, a_k$ （$k$ 是任意可行正整数）的乘积形式：$x = a_1 \times a_2 \times \cdots \times a_k$。$a_i$ 只能有一个质因子，且对于 $\forall \ i \neq j$，都满足 $\gcd(a_i, a_j) = 1$，即两个数互质。
分解之后，这些正整数的和 $\sum a_i$ 就是这个数的价值。特殊定义：$1$ 的价值是 $0$ 。
多组询问，每次给定正整数 $L, R$，求大小在 $L \sim R$ 范围内的所有数的价值之和。
限制：
- $1 \leqslant T \leqslant 10^4$
- $1 \leqslant L \leqslant R \leqslant 3 \times 10^7$
算法分析
做法：欧拉筛
使用 ps 数组记录当前已经筛出的质数，使用 val[x] 记录 $x$ 的价值
原理：欧拉筛中通过 if (i%ps[j] == 0) break; 控制每个合数只能被它的最小质因子标记，使得使得时间复杂度达到线性。
对于质数 $i$：val[i] = i
对于合数 i*ps[j] 有两种情况：
- $i$ 的最小质因子大于 $ps[j]$，那么
val[i*ps[j]] = val[i] + ps[j] - $i$ 的最小质因子等于 $ps[j]$，那么先分解出 $i$ 里面 $ps[j]$ 的最大次幂因子 $x$，那么
val[i*ps[j]] = val[i] - x + ps[j]*x
然后通过前缀和预处理，每次询问做差分即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const int MX = 3e7+5;
int ps[MX/10], pf[MX];
ll val[MX];
void init() {
int c = 0;
for (int i = 2; i < MX; ++i) {
if (!pf[i]) ps[++c] = i, pf[i] = i, val[i] = i;
for (int j = 1; i*ps[j] < MX; ++j) {
if (i%ps[j] == 0) {
pf[i*ps[j]] = pf[i]*ps[j];
val[i*ps[j]] = val[i] - pf[i] + pf[i*ps[j]];
break;
}
else {
pf[i*ps[j]] = ps[j];
val[i*ps[j]] = val[i] + ps[j];
}
}
}
for (int i = 1; i < MX; ++i) val[i] += val[i-1];
}
int main() {
freopen("stupid.in", "r", stdin);
freopen("stupid.out", "w", stdout);
init();
int t;
cin >> t;
while (t--) {
int l, r;
cin >> l >> r;
--l;
cout << val[r]-val[l] << '\n';
}
return 0;
}
12. 约数个数
给定 $n$ 个正整数 $a_i$，请你输出这些数的乘积的约数个数，答案对 $10^9+7$ 取模。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant a_i \leqslant 2 \times 10^9$
算法分析
$a$ 的标准分解：$a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$
$\tau (a) = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
vector<P> factorize(int n) {
vector<P> res;
for (int i = 2; i*i <= n; ++i) {
if (n%i != 0) continue;
res.emplace_back(i, 0);
while (n%i == 0) {
n /= i;
res.back().second++;
}
}
if (n != 1) res.emplace_back(n, 1);
return res;
}
int main() {
int n;
cin >> n;
map<int, int> mp;
rep(i, n) {
int a;
cin >> a;
auto fs = factorize(a);
for (auto [d, x] : fs) mp[d] += x;
}
mint ans = 1;
for (auto p : mp) ans *= p.second+1;
cout << ans << '\n';
return 0;
}
13. Counting Divisors
给定 $n$ 个整数，要求输出每个数的约数个数。
限制：
- $1 \leqslant n \leqslant 10^5$
- $1 \leqslant x \leqslant 10^6$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
vector<P> factorize(int n) {
vector<P> res;
for (int i = 2; i*i <= n; ++i) {
if (n%i != 0) continue;
res.emplace_back(i, 0);
while (n%i == 0) {
n /= i;
res.back().second++;
}
}
if (n != 1) res.emplace_back(n, 1);
return res;
}
int main() {
int n;
cin >> n;
rep(i, n) {
int a;
cin >> a;
int ans = 1;
auto fs = factorize(a);
for (auto [d, x] : fs) {
ans *= (x+1);
}
cout << ans << '\n';
}
return 0;
}
14. 约数之和
给定 $n$ 个正整数 $a_i$，请你输出这些数的乘积的约数之和，答案对 $10^9+7$ 取模。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant a_i \leqslant 2 \times 10^9$
算法分析
$a$ 的约数个数总和为 $\sigma(a) = \frac{p_1^{\alpha_1 + 1}}{p_1 - 1} \cdot \cdots \cdot \frac{p_k^{\alpha_k + 1}}{p_k - 1}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
vector<P> factorize(int n) {
vector<P> res;
for (int i = 2; i*i <= n; ++i) {
if (n%i != 0) continue;
res.emplace_back(i, 0);
while (n%i == 0) {
n /= i;
res.back().second++;
}
}
if (n != 1) res.emplace_back(n, 1);
return res;
}
int main() {
int n;
cin >> n;
map<int, int> mp;
rep(i, n) {
int a;
cin >> a;
auto fs = factorize(a);
for (auto& [p, x] : fs) mp[p] += x;
}
mint ans = 1;
for (auto [p, x] : mp) {
mint now = mint(p).pow(x+1)-1;
now /= p-1;
ans *= now;
}
cout << ans << '\n';
return 0;
}
15. P1593 因子和
输入两个整数 $a$ 和 $b$，求 $a^b$ 的因子和。
由于结果太大，只要输出它对 $9901$ 取模的结果。
限制：
- $1 \leqslant a \leqslant 5 \times 10^7$
- $0 \leqslant b \leqslant 5 \times 10^7$
算法分析
$a = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$
$ \Rightarrow a^b = p_1^{b\alpha_1}p_2^{b\alpha_2} \cdots p_k^{b\alpha_k} $
$ \Rightarrow \sigma(a^b) = \frac{p^{b\alpha_1+1} - 1}{p_1-1} \cdot \frac{p_2^{b\alpha+1}-1}{p_2-1} \cdots \frac{p_k^{b\alpha +1} - 1}{p_k - 1} $
注意：$9901$ 可能整除 $p-1$，所以需要特判一下。具体地，$9901 \Big| p-1 \Leftrightarrow p-1 \equiv 0 \pmod {9901} \Leftrightarrow p \equiv 1 \pmod {9901}$
$\Rightarrow \frac{p^{\alpha+1}-1}{p-1} = 1 + p + p^2 + \cdots + p^{\alpha} \equiv 1 + 1 + \cdots + 1 = \alpha+1\pmod {9901}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int mod = 9901;
//const int mod = 998244353;
// const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
vector<P> factorize(int n) {
vector<P> res;
for (int i = 2; i*i <= n; ++i) {
if (n%i != 0) continue;
res.emplace_back(i, 0);
while (n%i == 0) {
n /= i;
res.back().second++;
}
}
if (n != 1) res.emplace_back(n, 1);
return res;
}
int main() {
int a, b;
cin >> a >> b;
map<int, ll> mp;
auto fs = factorize(a);
for (auto [p, x] : fs) mp[p] = (ll)b*x;
mint ans = 1;
for (auto [p, x] : mp) {
if ((p-1)%mod == 0) {
ans *= x+1;
continue;
}
mint now = mint(p).pow(x+1)-1;
now /= p-1;
ans *= now;
}
cout << ans << '\n';
return 0;
}
16. Fraction Floor Sum
给定正整数 $N$，求 $\sum\limits_{i = 1}^N \lfloor \frac{N}{i} \rfloor$ 。
限制：
- $1 \leqslant n \leqslant 10^{12}$
算法分析
整除分块的性质
性质 $1$：$\lfloor \frac{n}{i} \rfloor$ 最多只有 $2\sqrt{n}$ 种取值
证明：对于 $i \leqslant \sqrt{n}$，最多只有 $\sqrt{n}$ 种取值。而对于 $i > \sqrt{n}$，有 $\frac{n}{i} < \sqrt{n}$，也最多只有 $\sqrt{n}$ 种取值，所以总的值最多不超过 $2\sqrt{n}$ 种。
性质 $2$：若 $\lfloor\frac{n}{r}\rfloor$ 与 $\lfloor\frac{n}{i}\rfloor$ 相等，那么 $r$ 的最大取值为 $\lfloor\frac{n}{\lfloor \frac{n}{i} \rfloor}\rfloor$
证明：设 $\lfloor \frac{n}{i} \rfloor = k$，于是如果 $r$ 取到比较大的数字，使得 $\lfloor \frac{n}{r} \rfloor$ 与 $\lfloor \frac{n}{i} \rfloor$不相等，那么 $\lfloor \frac{n}{r} \rfloor < k$，也即 $\frac{n}{r} < k$，也即 $r > \frac{n}{k}$，那么 $r > \lfloor \frac{n}{k} \rfloor$，即 $r > \lfloor\frac{n}{\lfloor \frac{n}{i} \rfloor}\rfloor$，所以 $r$ 最大取到 $\lfloor\frac{n}{\lfloor \frac{n}{i} \rfloor}\rfloor$ 可以使得 $\lfloor\frac{n}{r}\rfloor$ 与 $\lfloor\frac{n}{i}\rfloor$ 相等
有了上面两条性质，我们就可以定义两个变量 $l$ 和 $r$，每次计算一个相等的区间 $[l, r]$ 的值，乘以区间长度，然后计算下一个区间。区间个数是 $2\sqrt{n}$ 个，所以总复杂度是 $O(\sqrt{n})$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n;
cin >> n;
ll ans = 0;
for (ll i = 1; i <= n;) {
ll x = n/i;
ll ni = n/x+1;
ans += x*(ni-i);
i = ni;
}
cout << ans << '\n';
return 0;
}
17. Sum of Divisors
记 $\sigma(n)$ 表示整数 $n$ 的约数之和。比如，$\sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28$
要求计算 $\sum\limits_{i=1}^n \sigma(i) \mod {10^9 + 7}$ 。
限制：
- $1 \leqslant n \leqslant 10^{12}$
算法分析
注意到 $\sum\limits_{i=1}^n \sigma(i) = \sum\limits_{i=1}^n i\cdot \lfloor \frac{n}{i} \rfloor$
只需在上题的基础上稍微改动一下即可，也就是每段区间里每个数的贡献不再是 1，而是 $k \in [l, r]$，刚好成等差数列，那么这段区间对答案的贡献就是 $\lfloor \frac{n}{i} \rfloor \cdot \frac{(l+r)(r-l+1)}{2}$ 。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
ll n;
cin >> n;
mint ans;
for (ll i = 1; i <= n;) {
ll x = n/i;
ll ni = n/x+1;
ans += mint(x)*(ni-i)*(i+ni-1)/2;
i = ni;
}
cout << ans << '\n';
return 0;
}
18. 因数平方和
记 $f(x)$ 为 $x$ 的所有因数的平方的和。
例如：$f(12) = 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2$
定义 $g(n) = \sum\limits_{i=1}^n f(i)$ 。
给定 $n$，求 $g(n)$ 除以 $10^9+7$ 的余数。
限制：
- $1 \leqslant n \leqslant 10^9$
算法分析
注意到 $g(n) = \sum\limits_{i=1}^n f(i) = \sum\limits_{i=1}^n \sigma_2 (i) = \sum\limits_{i=1}^n i^2\cdot \lfloor \frac{n}{i} \rfloor$
其实推导到这里，就可以看出这题和上一题本质上是一样的，只是每段区间里从每个数的贡献为 $i$ 变成了 $i^2$，但区间里的 $i^2$ 序列的总和不太好处理，但我们可以利用前缀和来处理，也就是 $(1^2 + 2^2 + \cdots + j^2) - (1^2+2^2+\cdots + (i-1)^2)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint f(ll n) { return mint(n)*(n+1)*(2*n+1); }
int main() {
ll n;
cin >> n;
mint ans;
mint inv6 = mint(1)/6;
for (ll i = 1; i <= n;) {
ll x = n/i;
ll ni = n/x;
ans += mint(x)*(f(ni) - f(i-1))*inv6;
i = ni+1;
}
cout << ans << '\n';
return 0;
}
19. 除数函数求和 1
$\sigma_k (n) = \sum\limits_{d \mid n} d^k$
求 $\sum\limits_{i=1}^n \sigma_k (i)$ 对 $10^9 + 7$ 取模的结果。
限制：
- $1 \leqslant n, k \leqslant 10^7$
算法分析
$ \sum\limits_{i=1}^n \sigma_k (i) = \sum\limits_{i=1}^n \lfloor\frac{n}{i}\rfloor \cdot i^k $
注意到数据范围比较小，我们可以用线性筛筛出 $i^k$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int n, k;
// linear sieve
vector<int> ps, pf;
vector<mint> a;
void sieve(int mx) {
pf.resize(mx+1);
a.resize(mx+1);
a[1] = 1;
rep(i, mx + 1) pf[i] = i;
for (int i = 2; i <= mx; ++i) {
if (pf[i] == i) ps.push_back(i), a[i] = mint(i).pow(k);
rep(j, ps.size()) {
int x = ps[j]*i;
if (x > mx) break;
pf[x] = ps[j];
a[x] = a[i]*a[pf[x]];
}
}
}
int main() {
cin >> n >> k;
sieve(n);
mint ans;
for (int i = 1; i <= n; ++i) {
ans += a[i]*(n/i);
}
cout << ans << '\n';
return 0;
}
20. 正规数（二）
如果一个正整数的所有素因子均不超过 $5$，则它被称为正规数（Regular Number）。例如 $60$ 是一个正规数，因为 $60=2^2\cdot3\cdot5$ 也是一个正规数，因为 $1000=2^3\cdot5^3$。前十五个正规数为：
$$1, ~2, ~3, ~4, ~5, ~6, ~8, ~9, ~10, ~12, ~15, ~16, ~18, ~20, ~24$$
给定一个 $n$，请输出第 $n$ 个正规数。
限制：
- $1 \leqslant n \leqslant 1500$
算法分析
由于正规数要求所有素因子均不超过 $5$，那么素因子就只能是 $2$ 或 $3$ 或 $5$，于是这题就变成了 丑数 II
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n+1);
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= n; ++i) {
int num2 = dp[p2]*2, num3 = dp[p3]*3, num5 = dp[p5]*5;
dp[i] = min(min(num2, num3), num5);
if (dp[i] == num2) p2++;
if (dp[i] == num3) p3++;
if (dp[i] == num5) p5++;
}
cout << dp[n] << '\n';
return 0;
}
21. 无尽的循环
其实就是求解满足 $cx \equiv b-a \pmod {2^k}$ 的最小的 $x$
上面的同余式可转化成方程 $cx + 2^ky = b-a$
我们只需用 $\operatorname{exgcd}$ 求出 $cx + 2^ky = \gcd(c, 2^k)$ 的一组解 $(x, y)$，然后乘上 $\frac{b-a}{\gcd(c, 2^k)}$ 就能得到原方程的一组解
注意如果 $\gcd(c, 2^k) \not\mid (b-a)$ 则无解
现在我们找到了一组解 $x_0, y_0$ 满足
$$ cx_0 + 2^ky_0 = b-a $$
然后我们需要找一组 $x$ 最小的正整数解。
我们观察更一般的情况，即找到了一组解 $x_0, y_0$ 满足
$$ ax_0 + by_0 = \gcd(a, b) $$
在此基础上找一组 $x$ 最小的正整数解。
我们可以将所有的解用这组特殊解表示出来。设一个整数 $k$ 表示增量，那么有
$$ \begin{cases} x = x_0 + k\\\ y = y_0 - \frac{ak}{b} \end{cases} $$
因为 $y$ 是整数，所以有 $b \mid ak$，所以
$$ \frac{b}{\gcd(a, b)} \mid k $$
我们设 $d = \gcd(a, b)$，$k=\frac{bj}{d}$，那么
$$ \begin{cases} x=x_0 + \frac{b}{d} \cdot j \\\ y=y_0 - \frac{a}{d} \cdot j \end{cases} $$
因此将 $x_0$ 对 $\frac{b}{d}$ 取模就可以得到最小的解。
回到原问题：
$$ cx_0 + 2^ky_0 = b-a $$
那么答案就是 $p_0 \% \frac{2^k}{\gcd(c, 2^k)}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
// {g, x, y}: ax + by = g
array<ll, 3> exgcd(ll a, ll b) {
if (b == 0) return {a, 1, 0};
auto [g, x, y] = exgcd(b, a % b);
return {g, y, x - a / b * y};
}
int main() {
ll a, b, c; int k;
cin >> a >> b >> c >> k;
ll d = 1ll<<k;
auto [g, x, y] = exgcd(c, d);
if ((b-a)%g) puts("Inf");
else {
x *= (b-a)/g;
ll t = abs(d/g);
ll ans = x%t;
cout << (ans+t)%t << '\n';
}
return 0;
}
22. 不定方程
给定 $n$ 个整数 $a_1,a_2,\dots,a_n$ 作为上界，再给定一个整数 $m$，请问方程
$$x_1+x_2+\dots+x_n=m$$
有多少种不同的整数解且满足 $1 \leqslant x_i \leqslant a_i$。由于解的数量可能很大，输出答案模 $1,000,000,007$ 的余数。
限制：
- $1 \leqslant n \leqslant 20$
- $1 \leqslant m \leqslant 10^9$
- $1 \leqslant a_i \leqslant 10^6$
算法分析
注意到将每个 $a_i$ 减去 $1$，同时将 $m$ 减去 $n$，不会改变原题题意，而此时就变成了 Devu和鲜花
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
vector<mint> ifact;
void init(int n) {
ifact.resize(n+1);
mint fact = 1;
for (int i = 1; i <= n; ++i) fact *= i;
ifact[n] = fact.inv();
for(int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint comb(ll n, int r) {
mint x = 1;
rep(i, r) x *= n-i;
x *= ifact[r];
return x;
}
int main() {
int n; ll m;
cin >> n >> m;
m -= n;
if (m < 0) {
puts("0");
return 0;
}
init(n);
vector<ll> f(n);
rep(i, n) cin >> f[i], f[i]--;
mint ans;
rep(s, 1<<n) {
ll a = m;
rep(i, n) if (s>>i&1) a -= f[i]+1;
if (a < 0) continue;
mint now = comb(a+n-1, n-1);
if (__builtin_parity(s)) ans -= now;
else ans += now;
}
cout << ans << '\n';
return 0;
}
23. LCM Pattern
统计长度为 $N$ 且所有数的最小公倍数为 $M$ 的序列个数，并对结果模 $998244353$。
限制：
- $2 \leqslant N \leqslant 10^9$
- $1 \leqslant M \leqslant 10^9$
算法分析
单独考虑 $M$ 中的素因子
对于素因子 $p$，假设它在 $M$ 中的指数为 $a$，序列中包含素因子 $p$ 的数对应的指数一定不超过 $a$，同时至少存在一个数的因子包含 $p^a$
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
using mint = modint998244353;
vector<P> factorize(int n) {
vector<P> res;
for (int i = 2; i*i <= n; ++i) {
if (n%i != 0) continue;
res.emplace_back(i, 0);
while (n%i == 0) {
n /= i;
res.back().second++;
}
}
if (n != 1) res.emplace_back(n, 1);
return res;
}
int main() {
int n, m;
cin >> n >> m;
auto fs = factorize(m);
mint ans = 1;
for (auto [_, x] : fs) {
ans *= mint(x+1).pow(n) - mint(x).pow(n);
}
cout << ans.val() << '\n';
return 0;
}
24. Sum of Averages (subset)
给定长度为 $N$ 的序列 $A$。$A$ 有 $2^N-1$ 个非空子序列，请计算每个非空子序列的平均数，并输出它们的总和 $\bmod 998244353$。
限制：
- $1 \leqslant N \leqslant 2 \times 10^5$
- $1 \leqslant A_i \leqslant 10^9$
算法分析
考虑每个元素 $A_i$ 对答案的贡献
对于 $A_i$ 和整数 $k (k = 1, 2, \cdots, N)$，$A_i$ 包含在大小为 $k$ 的子序列的方案数为除了 $A_i$ 以外，还需在其他 $N-1$ 个数中选出 $k-1$ 个数的方案数，即 $\binom{N-1}{k-1}$。
因此，$A_i$ 对答案的贡献就是 $A_i \sum\limits_{k=1}^N\frac{\binom{N-1}{k-1}}{k}$
注意到 $\frac{\binom{N-1}{k-1}}{k} = \frac{(N-1)!}{(N-k)!k!} = \frac{N!}{(N-k)!k!N} = \frac{\binom{N}{k}}{N}$，那么有 $$\displaystyle \sum_{k=1}^N\frac{\binom{N-1}{k-1}}{k} = \sum_{k=1}^N \frac{\binom{N}{k}}{N} = \frac{(1+1)^N - \binom{N}{0}}{N} = \frac{2^N - 1}{N}$$
于是，最后的答案就是 $\frac{2^N - 1}{N} \sum\limits_{i=1}^N A_i$
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
mint ans;
rep(i, n) ans += a[i];
ans *= (mint(2).pow(n)-1)/n;
cout << ans.val() << '\n';
return 0;
}
25. 大数的幂
计算 $N^M \bmod 129402307$
限制：
- $0 \leqslant N, M \leqslant 10^{10^5}$
算法分析
注意到这里的模数是个素数，所以可以考虑费马小定理
费马小定理：
若 $p$ 为素数，$\gcd(n, p) = 1$，则 $n^{p-1} \equiv 1 \pmod p$
分为 $\gcd(n, p) = 1$ 和 $\gcd(n, p) \neq 1$ 两种情况：
- $\gcd(n, p) = 1$，则 $n^m \equiv n^{m \% (p-1)} \pmod p$
- $\gcd(n, p) \neq 1$，($n$ 一定是 $p$ 的倍数)，则分为 $m = 0$ 和 $m \neq 0$ 两种情况：
- $m = 0$，则 $n^0 \equiv 1 \pmod p$
- $m \neq 0$，则 $n^m \equiv 0 \pmod p$
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 129402307;
//const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
ll f(string s, int p=mod) {
ll res = 0;
for (char c : s) {
res = (res*10 + (c-'0'))%p;
}
return res;
}
int main() {
string s, t;
cin >> s >> t;
ll a = f(s), b = f(t, mod-1);
if (a != 0) cout << mint(a).pow(b) << '\n';
else {
if (t[0] == '0') puts("1");
else puts("0");
}
return 0;
}
26. [Cnoi2019] 数学作业
给定长度为 $n$ 的序列 $a$，找出 $a$ 的所有子集的异或和再求和。
- $1 \leqslant n \leqslant 3 \times 10^6$
算法分析
见 LC 1863
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int as = 0;
rep(i, n) {
int a;
cin >> a;
as |= a;
}
mint ans = mint(2).pow(n-1)*as;
cout << ans << '\n';
}
return 0;
}
27. Sum of N
定义 $f(X)$ 为除了 $X$ 自身以外 $X$ 的最大因子。比如，$f(12) = 6$，$f(7) = 1$。
注意，将 $f(1)$ 定义为 $0$。
给定整数 $K$，找到所有满足 $f(N) = K$ 的 $N$ 的总和。
可以证明答案在题目所给限制范围下不超过 $10^{18}$ 。
要求支持多测
限制：*
- $1 \leqslant T \leqslant 10^4$
- $2 \leqslant K \leqslant 10^6$
算法分析
首先，注意到 $f(N) = \frac{N}{p}$，其中 $p$ 是 $N$ 的最小素因子。
所以，如果我们希望 $f(N) = K$，那么一定有 $N = K \cdot p$，其中 $p$ 是 $N$ 的最小素因子。
具体地，选择不同的 $p$ 会得到不同的 $N$，所以我们可以转而去关注可能选哪个 $p$ 。
因为 $N = K \cdot p$，$N$ 的除了素因子 $p$ 以外的每个素因子同时也是 $K$ 的素因子。
特别地，令 $q$ 为 $K$ 的最小素因子。
则有：
- 如果 $p > q$，由于 $q$ 也整除 $N$，所以 $p$ 一定不是 $N$ 的最小素因子
- 如果 $p \leqslant q$，$p$ 一定是 $N$ 的最小素因子
所以，唯一的合法的 $N$ 能表示为 $K \cdot p$，其中 $p$ 是不超过 $q$ 的素数。
代码实现
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
// linear sieve
vector<bool> isp;
vector<int> ps, pf;
vector<ll> sum;
void sieve(int mx) {
isp.resize(mx+1);
pf.resize(mx+1);
sum.resize(mx+1);
rep(i, mx+1) pf[i] = i;
for (int i = 2; i <= mx; ++i) {
sum[i] = sum[i-1];
if (pf[i] == i) isp[i] = true, ps.push_back(i), sum[i] += i;
rep(j, ps.size()) {
int x = ps[j] * i;
if (x > mx) break;
pf[x] = ps[j];
}
}
}
void solve() {
int k;
cin >> k;
int p = pf[k];
ll ans = sum[p]*k;
cout << ans << '\n';
}
int main() {
sieve(1e6);
int t;
cin >> t;
while (t--) solve();
return 0;
}
28. Graph Paths I
给定一张有 $n$ 个点和 $m$ 条边的有向无权图。
要求计算从点 $1$ 到点 $n$ 且恰经过 $k$ 条边的路径数。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant m \leqslant n(n-1)$
- $1 \leqslant k \leqslant 10^9$
算法分析
矩阵快速幂，具体可以参考 EDPC-R
注意：本题可能有重边
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
template<typename T>
struct Matrix {
int h, w;
vector<vector<T>> d;
Matrix() {}
Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}
Matrix& unit() {
assert(h == w);
rep(i,h) d[i][i] = 1;
return *this;
}
const vector<T>& operator[](int i) const { return d[i];}
vector<T>& operator[](int i) { return d[i];}
Matrix operator*(const Matrix& a) const {
assert(w == a.h);
Matrix r(h, a.w);
rep(i,h)rep(k,w)rep(j,a.w) {
r[i][j] += d[i][k]*a[k][j];
}
return r;
}
Matrix pow(long long t) const {
assert(h == w);
if (!t) return Matrix(h,h).unit();
if (t == 1) return *this;
Matrix r = pow(t>>1);
r = r*r;
if (t&1) r = r*(*this);
return r;
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
Matrix<mint> d(n, n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
d[a][b] += 1;
}
d = d.pow(k);
mint ans = d[0][n-1];
cout << ans << '\n';
return 0;
}
29. Graph Paths II
给定一张有 $n$ 个点和 $m$ 条边的有向带权图。
要求计算从点 $1$ 到点 $n$ 且恰经过 $k$ 条边的最短路。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant m \leqslant n(n-1)$
- $1 \leqslant k \leqslant 10^9$
算法分析
只需将矩阵快速幂中的矩阵乘法部分改成floyd即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<typename T>
struct Matrix {
int h, w; T val;
vector<vector<T>> d;
Matrix() {}
Matrix(int h, int w, T val=0): h(h), w(w), val(val), d(h, vector<T>(w,val)) {}
Matrix& unit() {
assert(h == w);
rep(i,h) d[i][i] = 0;
return *this;
}
const vector<T>& operator[](int i) const { return d[i];}
vector<T>& operator[](int i) { return d[i];}
Matrix operator*(const Matrix& a) const {
assert(w == a.h);
Matrix r(h, a.w, val);
rep(k,w)rep(i,h)rep(j,a.w) {
r[i][j] = min(r[i][j], d[i][k]+a[k][j]);
}
return r;
}
Matrix pow(long long t) const {
assert(h == w);
if (!t) return Matrix(h,h,val).unit();
if (t == 1) return *this;
Matrix r = pow(t>>1);
r = r*r;
if (t&1) r = r*(*this);
return r;
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
const ll INF = 2e18;
Matrix<ll> d(n, n, INF);
rep(i, m) {
int a, b; ll c;
cin >> a >> b >> c;
--a; --b;
d[a][b] = min(d[a][b], c);
}
d = d.pow(k);
ll ans = d[0][n-1];
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}
30. 随机游走2
题意转化：
假设输入的偶数为 $2n$，其中竖直方向为走了 $2k$ 步，那么水平方向走了 $2(n-k)$ 步，然后做带重复的全排列：
$ \begin{aligned} ans &= \sum_{k = 0}^n \frac{(2n)!}{(k!)^2((n-k)!)^2} = \sum_{k = 0}^n \frac{(2n)!}{n! \cdot n!} \cdot \frac{n! \cdot n!}{(k!)^2((n-k)!)^2}\\\ &= \sum_{k = 0}^n \binom{2n}{n} \cdot \binom{n}{k}^2 \\\ &= \binom{2n}{n} \sum_{k = 0}^n \binom{n}{k} \cdot \binom{n}{n-k} \\\ &= \binom{2n}{n}^2 \end{aligned} $
31. Dice Probability
你掷一枚骰子 $n$ 次，每掷一次骰子都会得到一个 $1 \sim 6$ 之间的随机值。
要求计算最后得到的总和在 $a$ 和 $b$ 之间的概率。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant a \leqslant b \leqslant 6n$
算法分析
概率dp
记 dp[i][j] 表示掷前 $i$ 次骰子得到的总和为 $j$ 的概率
时间复杂度为 $\mathcal{O}(36n^2)$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
double dp[105][605];
int main() {
int n, a, b;
cin >> n >> a >> b;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
rep(j, 6*n+1) {
double now = 0;
for (int x = 1; x <= 6; ++x) {
if (j >= x) now += dp[i-1][j-x];
}
dp[i][j] = now/6;
}
}
double ans = 0;
for (int i = a; i <= b; ++i) ans += dp[n][i];
printf("%.6f\n", ans);
return 0;
}
32. Candy Lottery
有 $n$ 个小朋友，给每个小朋友随机分配 $i$ 个糖果，其中 $i$ 是区间 $[1, k]$ 之间的任意整数。
求一个小朋友获得最多的糖果的期望值。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant k \leqslant 100$
算法分析
对于 $i = 1, 2, \cdots, k$，先求出使得最大值为 $i$ 的概率。这个等于 $(\frac{i}{k})^n - (\frac{i-1}{k})^n$。因为我们可以先随机从 $1 \sim i$ 中选出 $n$ 个数，每个数被选择的概率为 $\frac{i}{k}$，再减去 $i$ 不出现在其中的情况即可。然后将每个概率分别乘上对应的权值 $i$ 就得到了问题的答案。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, k;
cin >> n >> k;
double ans = 0;
for (int i = 1; i <= k; ++i) {
double a = 1, b = 1;
rep(j, n) {
a *= 1.*i/k;
b *= 1.*(i-1)/k;
}
ans += (a-b)*i;
}
printf("%.6f\n", ans);
return 0;
}
33. Various Arrays（★5）
高桥要构造一个数列 $a$，数列 $a$ 的第 $i$ 项元素 $a_i$ 的取值为等概率地随机从 $[l_i, r_i]$ 中任选一个数。求他构造的数列 $a$ 的逆序对的期望值。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant l_i \leqslant r_i \leqslant 100$
算法分析
期望的线性性
先求出任意两个数的逆序对的期望，再将它们累加起来即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> l(n), r(n);
rep(i, n) cin >> l[i] >> r[i];
double ans = 0;
rep(i, n)rep(j, i) {
int tot = 0, cnt = 0;
for (int x = l[i]; x <= r[i]; ++x) {
for (int y = l[j]; y <= r[j]; ++y) {
++tot;
if (y > x) ++cnt;
}
}
ans += 1.*cnt/tot;
}
printf("%.10f\n", ans);
return 0;
}
34. Ajust
给定整数 $N$ 和长度为 $2N$ 的字符串 $S$。其中 $S$ 仅由字符 0 和 1 构成，且各有 $N$ 个。
遍历所有满足以下条件的 $(1, 2, \cdots, 2N)$ 的排列 $P$ 总共 $(N!)^2$ 个，要求每个排列的逆序数的总和，并对结果模 $998244353$。
- 对于任意 $1 \leqslant i \leqslant 2N$，$P_i \leqslant N \Leftrightarrow S_i = 0$
限制：
- $1 \leqslant N \leqslant 2 \times 10^5$
算法分析
一个经典结论：
$(1, 2, \cdots, N)$ 的全排列的逆序数的总和为 $\frac{1}{2} \cdot \binom{N}{2} \cdot N!$
考虑三种贡献：
- $0$ 和 $0$ 之间
- $1$ 和 $1$ 之间
- $0$ 和 $1$ 之间
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
// using mint = modint998244353;
using ll = long long;
const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
struct modinv {
int n; vector<mint> d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(-d[mod%n]*(mod/n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
int n; vector<mint> d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*n), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
int n; vector<mint> d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*invs(n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
if (n < k || k < 0) return 0;
return facts(n)*ifacts(k)*ifacts(n-k);
}
template<typename T>
struct BIT {
int n;
vector<T> d;
BIT(int n=0):n(n),d(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
d[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += d[i];
}
return x;
}
T sum(int l, int r) {
return sum(r-1) - sum(l-1);
}
};
int main() {
int n;
string s;
cin >> n >> s;
int a = 0, b = n;
int n2 = n*2;
vector<int> p(n2);
rep(i, n2) {
if (s[i] == '0') p[i] = a++;
else p[i] = b++;
}
mint ans;
BIT<int> t(n2);
rep(i, n2) {
ans += i-t.sum(p[i]);
t.add(p[i]);
}
ans += mint(n)*(n-1)/2;
ans *= facts(n).pow(2);
cout << ans << '\n';
return 0;
}
35. 随机gcd
对于一个上界 $n$ 和一个正整数 $m\leq n$，考虑如下随机过程：
- 在 $[1,n]$ 中均匀随机地选择整数 $p$，令 $m\gets \gcd(m,p)$。
该过程会不停执行，直到 $m=1$。令 $E(m,n)$ 表示这个过程的期望执行步数。
对 $1\leq m\leq n$ 的每个 $m$ 求 $E(m,n)$ 在模 $(10^9+7)$ 意义下的值。
限制：
- $1\leq n\leq 5\times 10^5$
算法分析
令 $dp(m) = E(m, n)$，$dp(1) = 0$
当 $m > 1$ 时，$\displaystyle dp(m) = \sum_{p=1}^n \frac{1}{n}(1 + dp(\gcd(m, p)))$。
由于 $\gcd(m, p) \leqslant m$，只需要把 $\gcd(m, p) = m$ 的 $p$ 移项使得 $\gcd(m, p) < m$ 就可以递推了：设有 $k$ 个 $p$ 使得 $\gcd(m, p) = m$，则
$$dp(m) = \frac{n}{n-k}\left(1 + \frac{1}{n}\sum_{\gcd(m, p) < m} dp(\gcd(m, p))\right)$$
为了加速计算 $\displaystyle \sum_{\gcd(m, p) < m} dp(\gcd(m, p))$，钦定 $m$ 的某个因子 $g = \gcd(m, p)$，$m = g \cdot s$，尝试找到 $1 \leqslant p \leqslant n$ 的数量使得 $\gcd(m, p) = g$，如果有 $\gcd(g \cdot s, g \cdot t) = g$，那么 $\gcd(s, t) = 1$，由 $g \cdot t \leqslant n$，得到 $t \leqslant \frac{n}{g}$，于是问题转为求 $[1, \frac{n}{g}]$ 中与 $s = \frac{m}{g}$ 互质的数的个数，这可以通过对 $s$ 的质因子容斥来完成。具体地，设 $s$ 的质因子集合为 $S = \{p_1, \cdots, p_k\}$，$M = \frac{n}{g}$，那么这样的数的个数就有 $\displaystyle \sum_{T \subseteq S} (-1)^T \left\lfloor\frac{M}{\prod_{p_i \in T} p_i}\right\rfloor$ 个，在此数据范围下 $k \leqslant 6$ .
于是我们以 $d(m)k2^k$ 的复杂度完成了 $dp(m)$ 的计算，总复杂度即为 $O(n\log n \cdot k2^k)$，其中 $k = 6$，可以通过。使用一些位运算技巧可以使复杂度降为 $O(n\log n \cdot 2^k)$ 。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n;
cin >> n;
vector<vector<int>> ds(n+1);
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i) {
ds[j].push_back(i);
}
}
vector<mint> dp(n+1);
for (int i = 2; i <= n; ++i) {
int m = ds[i].size();
vector<int> cnt(m);
rep(j, m) cnt[j] = n/ds[i][j];
for (int j = m-1; j >= 0; --j) {
for (int k = j+1; k < m; ++k) {
if (ds[i][k]%ds[i][j] == 0) {
cnt[j] -= cnt[k];
}
}
}
dp[i] = n;
rep(j, m-1) dp[i] += dp[ds[i][j]]*cnt[j];
dp[i] /= n-cnt[m-1];
}
for (int i = 1; i <= n; ++i) cout << dp[i] << ' ';
return 0;
}
36. Counting Necklaces
统计有多少种不同的项链，项链由 $n$ 颗珠子构成且每颗珠子有 $m$ 种可能的颜色。并对结果模 $10^9 + 7$
将两种项链视为不同的当且仅当不能通过旋转其中一个得到另一个。
限制：
- $1 \leqslant n, m \leqslant 10^6$
算法分析
考虑 Polya定理：
$$ L = \frac{1}{|G|}\sum_{i=1}^{|G|} m^{C(a_i)} $$
这里有 $n$ 种可能的旋转，所以置换群的大小是 $n$. 另外，$C(a_i) = \gcd(n, i)$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n, m;
cin >> n >> m;
mint ans;
rep(i, n) ans += mint(m).pow(gcd(n, i));
ans /= n;
cout << ans << '\n';
return 0;
}
注：随缘更新
$orz$