1174E

非常好题目，使我的大脑旋转（？） 还是一样，介绍思路。 既然题目让我们计算 \(f_{\max}(n)\) 的数量，则先考虑 \(f_{\max}(n)\) 的值怎样求得。容易发现，设 \(n=\prod p_i^{k_i},p_i\in \operatorname{prime}\) ，则 \(f( ......

[题目链接](https://codeforces.com/problemset/problem/1174/E) ## description 给定 $n\leq 10^6$, 求有多少个 $1$ 到 $n$ 的排列，对于一个 1 到 $n$ 的排列 $p$，$f(p)$ 表示 $p$ 的任意前缀内 ......

## 题意 对于一个排列 $p$，定义 $g$ 为 $p$ 的前缀最大公约数序列，即 $g_i = \gcd\limits_{j = 1}^{i} p_j$。定义 $f(p)$ 为 $g$ 的元素种类数。 给定 $n$，求长度为 $n$ 的且使得 $f(p)$ 取最大值的排列个数，对 $10^9 + ......