数论

题目大意 即求 $$ S (n) = \sum^n_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k f (\gcd \{ a_x \}) \gcd \{ a_x \} $$ 我自己随便简写了，全打太麻烦了。 分析 这东西看着很吓人，其实是纸老虎。首先 $f(x) = \mu(x)^2$。提出 $\gcd$ 有 $$ \begin{aligned} S (n) & =\sum_{d=1}^{n}\sum^{n}_{\{ a_{x}\}=1}(\prod_{j=1}^{x}a_{j})^{k}{\mu}(d)^{2}d [gcd \{ a_{x}\} =d]\\ & =\sum_{d=1}^{n}{\mu}(d)^{2}d^{k x+1}\sum^{n/d}_{\{ a_{x}\} =1}(\prod_{j=1}^{x}a_{j})^{k}[gcd \{ a_{x}\} =1] \end{aligned} $$ 对后面这部分反演有 $$ \begin{aligned} & \sum^{n / d}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \left( \sum_{t \mid \gcd \{ a_x \}} \mu (t) \right)\\ = & \sum^{n / d}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \left( \sum_{t = 1}^{n / d} [t \mid \gcd \{ a_x \}] \mu (t) \right)\\ = & \sum_{t = 1}^{n / d} \mu (t) t^{k x} \sum^{n / d t}_{\{ a_x \} = 1} \left( \prod_{j = 1}^x a_j \right)^k \end{aligned} $$...

题目大意 设 Fibonacci 数列第 $i$ 项为 $F_i$，求 $$ S = \sum_{i = 0}^n (F_{i c})^k $$ 分析 由特征方程法，设 $$ x^2 + x - 1 = 0 \Longrightarrow A, B = \frac{1 \pm \sqrt{5}}{2} $$ 因此 Fibonacci 通项公式即可表示为 $$ F_n = \frac{A^n - B^n}{A - B} $$ 根据二次剩余的知识，模意义下是可以开方的。因此 $$ (F_{i c})^k = \left( \frac{A^{i c} - B^{i c}}{A - B} \right)^k = \frac{1}{(A - B)^k} \sum_{j = 0}^k \binom{k}{j} (- 1)^{k - j} (A^j B^{k - j})^{i c} $$...

题目大意 定义 $f(n, k)$ 为满足如下要求的，长度为 $k$ 的数列 $\\{a_i\\}$ 个数： 要求每个数字都大于 $1$； 数列各项之积恰为 $n$。 求其前缀和 $S(n, k) = \sum f(i, k)$。 分析 多组输入好坑啊。 先允许 $a_i=1$，将结果记为 $g(n,k)$，容易利用隔板法求得 $$ g (p^c, k) = \binom{t + k - 1}{k - 1} $$ 对于多个质因数，显然其贡献是相互独立的，即 $g$ 是积性函数。考虑选取 $i$ 个数令其 $a_i>1$，枚举有 $$ g (n, k) = \sum_{i = 1}^k \binom{n}{i} f (n, i) $$ 二项式反演（或者直接容斥）有 $$ f (n, k) = \sum_{i = 1}^k (- 1)^{k - i} \binom{k}{i} g (n, i) $$...

题目大意 定义 $$ f (n) = \sum_{d \mid n} d \left[ \gcd \left( d, \frac{n}{d} \right) = 1 \right] $$ 求其前缀和 $S(n)$。 分析 首先 Min25 筛是过不了的，内存不够。先推式子 $$ \begin{aligned} S (n) &= \sum_{i = 1}^n \sum_{d \mid i} d \left[ \gcd \left( d, \frac{i}{d} \right) = 1 \right] \\ &= \sum_{d = 1}^n \sum_{i = 1}^n d [d \mid i] \left[\gcd \left( d, \frac{i}{d} \right) = 1 \right] \\ &= \sum_{d = 1}^n \sum_{i = 1}^{n / d} d [\gcd (i, d) = 1] \end{aligned} $$...

题目大意 即求 $$ S = \sum_{n=0}^\infty f(n)r^n $$ 分析 换序 $$ S = \sum_{n = 0}^{\infty} \left( \sum_{i = 0}^m f_i n^i \right) r^n = \sum_{i = 0}^m f_i \sum_{n = 0}^{\infty} n^i r^n $$ 令 $$ S_i = \sum_{n = 0}^{\infty} n^i r^n $$ 套路的逐项相减，主动的凑二项式 $$ (1 - r) S_i = 1 + \sum_{n = 1}^{\infty} n^i r^n - \sum_{n = 1}^{\infty} (n - 1)^i r^n = 1 + \sum_{n = 0}^{\infty} r^{n + 1} \sum_{j = 0}^{i - 1} \binom{k}{j} n^j $$...

题目大意 给定积性函数 $f(p^c) = p \oplus c$。对 $1000000007$ 取模求前缀和。 分析 Min25 板子题。 const ll mod = 1000000007, inv2 = 500000004; const int maxn = 200001; ll n, prime[maxn], cnt, w[maxn], s[maxn], c[maxn]; ll sqrt_n, m; ll mo(ll x) { return (x + mod) % mod; } ll f_p(ll p, ll e) { return p ^ e; } int id(ll x) { return x <= sqrt_n ? x : m - (n / x) + 1; } ll F(long long n, int k) { if (n <= prime[k]) return 0; ll ret = s[id(n)] - s[prime[k]]; for (int i = k + 1; i <= cnt && prime[i] * prime[i] <= n; i++) { ll pi = prime[i], pk = pi; for (int c = 1; pk * pi <= n; c++, pk *= pi) ret += f_p(pi, c) * F(n / pk, i) + f_p(pi, c + 1); } return mo(ret); } int main() { n = rr(); sqrt_n = sqrt(n + 0....

题目大意 即求 $$ \sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) \in \mathbb{P}] $$ 分析 先转化一下 $$ \sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) \in \mathbb{P}] = \sum_{p}\sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) = p] $$ 在 P2522 中得到 $$ \sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j) = k] = \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tk} \right\rfloor \left\lfloor \frac{y}{tk} \right\rfloor $$ 代入有 $$ \sum_{p} \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tp} \right\rfloor \left\lfloor \frac{y}{tp} \right\rfloor $$ 令 $T = tp$，$T$ 的上界应还是 $\min(x,y)$，代入有 $$ \sum_{T=1}^{\min(x,y)} \left\lfloor \frac{x}{T} \right\rfloor \left\lfloor \frac{y}{T} \right\rfloor \sum_{p \mid T} \mu\left(\frac{T}{p}\right) $$...

题目大意 设 $$ \varphi_{x+1}(m) = \varphi(\varphi_x(m)) $$ 求最小的 $x$ 使得 $\varphi_x(m) = 1$。 其中 $\varphi(m)$ 是欧拉函数。 分析 注意到仅有 $\varphi(1) = \varphi(2) = 1$，再有公式 $$ \varphi\left(\prod_{i=1}^mp_i^{q_i}\right) = \prod_{i=1}^m(p_i-1)p_i^{q_i-1} $$ 因此从唯一分解形式的角度来看，迭代一次消去了一个 $2$，也生成了一些 $2$。 考虑设 $f(n)$ 为 $\varphi(n)$ 中因子 $2$ 的个数。 设 $\gcd(a,b) = 1$，可以证明 $f(ab) = f(a) f(b)$。同时 $f(p) = f(p-1)$。 这说明 $f(x)$ 是一个积性函数，可以用 Euler 筛递推。 const ll MN = 1e5 + 10; bool notp[1000001]; int prime[200001], cnt, phi[1000001]; void sieve(int n) { phi[1] = 1; for (ll i = 2; i <= n; i++) { if (!...

Berland 年有 $m$ 月，每月 $d$ 天。一周有 $w$ 天。 若第 $x$ 月的第 $y$ 天和第 $y$ 月的第 $x$ 天是同一个星期，则称 $(x,y)$ 是一对。 求一年有几对。 $$ xd+y \equiv yd+x \pmod w $$ 即 $$ (x-y)(d-1) \equiv 0 \Rightarrow (x-y)(d-1) \in w\mathbb{Z} $$ 于是有 $$ y-x = \frac{wk}{\gcd(w,d-1)} $$ 又 $x < y \leqslant \min(m,d)$​， int main() { ll ttt = rr(); while (ttt--) { ll m = rr(), d = rr(), w = rr(); ll g = w / gcd(w, d - 1); ll max_y = min(m, d) - 1; ll div = (max_y + 1) / g, mod = (max_y + 1) % g; ll sum = (div - 1) * div / 2 * g + mod * div; printf("%lld\n", sum); } return 0; }

题目大意 即求 $$ \sum_{i=1}^n \gcd(i,n) $$ 分析 联想到 $$ \varphi(n) = \sum_{i=1}^n [\gcd(i,n) = 1] $$ 尝试凑这个形式 $$ \begin{aligned} \sum_{i=1}^n \gcd(i,n) &= \sum_{d \mid n} d \sum_{i=1}^n [\gcd(i,n) = d] \\ &= \sum_{d \mid n} d \sum_{i=1}^{n/d} [\gcd(i,n/d) = 1] \\ &= \sum_{d \mid n} d \varphi(n/d) \end{aligned} $$ 这里其实已经可以过题了，但还可以再瞎搞一下，令 $$ nf(n) = \sum_{d \mid n} d \varphi(n/d) = n\sum_{d \mid n} \frac{\varphi(d)}{d} $$ 尝试证明 $f(n)$ 是一个积性函数。设 $\gcd(a,b) = 1$，有...