我也不知道我是不是糖丸

模拟赛碰到一个很纸张的题目，但是自己没有做出来，于是记一下。

description

\(1 \le n, a_i \le 3 \times 10^5\)。

solution

首先场上我写了一个很典的暴力做法。

考虑到预处理出所有阶乘的质因子幂次，然后相当于我从大往小枚举，能除多少就除多少，这样肯定能够满足字典序最大，然后发现除法对应到质因子幂次上就变成了减法，于是就变成了一个求最大的 \(c\) 使得 \(a - c \times b \ge 0\)，直接除一下就做完了，放带代码：

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 3e5 + 5;int n;
int a[N], prime[N];
vector < int > p;
vector < pair < int, int > > ans;
vector < int > chifan[N], szy;void init () {for ( int i = 2; i <= 7000; i ++ ) {if ( !prime[i] ) {for ( int j = i + i; j <= 7000; j += i ) {prime[j] = 1;}}}
}signed main () {freopen ( "secure.in", "r", stdin );freopen ( "secure.out", "w", stdout );ios :: sync_with_stdio ( false );cin.tie ( 0 ), cout.tie ( 0 );cin >> n;init ();for ( int i = 2; i <= 7000; i ++ ) {if ( !prime[i] ) {p.push_back ( i );}}for ( int i = 2; i <= 7000; i ++ ) {int tmp = i;for ( int j = 0; j < p.size (); j ++ ) {int cnt = 0;while ( tmp % p[j] == 0 ) {cnt ++;tmp /= p[j];}chifan[i].push_back ( cnt );}}for ( int i = 3; i <= 7000; i ++ ) {for ( int j = 0; j < p.size (); j ++ ) {chifan[i][j] += chifan[i - 1][j];}}for ( int i = 0; i < p.size (); i ++ ) {szy.push_back ( 0 );}for ( int i = 1; i <= n; i ++ ) {cin >> a[i];if ( a[i] != 1 ) {for ( int j = 0; j < p.size (); j ++ ) {szy[j] += chifan[a[i]][j];}}}for ( int i = 7000; i >= 2; i -- ) {int mini = 1e18;for ( int j = 0; j < p.size (); j ++ ) {if ( chifan[i][j] ) {mini = min ( mini, szy[j] / chifan[i][j] );}}if ( mini ) {ans.push_back ( { i, mini } );for ( int j = 0; j < p.size (); j ++ ) {szy[j] -= mini * chifan[i][j];}}}cout << ans.size () << '\n';for ( pair < int, int > x : ans ) {cout << x.first << " " << x.second << '\n';}return 0;
}

但是很明显，这样做是 \(O(nV)\) 的，非常不好，我们考虑优化。

发现从大往小枚举阶乘的过程中，相当于我乘上一个 \(\frac{1}{i}\)，对应的质因子幂次减去一个数，发现更改项最多是质因子个数级别，也就是 \(O(\log V)\) 级别，于是我们可以暴力在线段树上更改，然后我们要求的就是 \(a_i - c \times b_i\)，这个东西我们转化成 \(\frac{a}{b}\)，然后求一个最小值，和区间和即可。

代码：