我也不知道我是不是糖丸

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

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 long

using 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}\)，然后求一个最小值，和区间和即可。其实我也可以维护一个 \(a_i\) 真实值为 \(a_i - c \times b_i\) 的标记，考虑到每次单点修改直接把 tag 更新赋值为 \(0\) 就好

代码（因为我懒所以复制的 ChiFAN 的代码）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5+114;
int pri[maxn];
void init(){
    for(int i=2;i<maxn;i++){
        if(pri[i]==0){
            for(int j=2;i*j<maxn;j++) pri[i*j]=i;
        }
    }
}
const int inf = 1e18+114;
vector< pair<int,int> > d[maxn];
int cnt[maxn],now[maxn];
int top = 3e5+100;
multiset<int> S;
int n;
int a[maxn];
int b[maxn];
vector< pair<int,int> > ans;
int tr[maxn<<2];//min(cnt/now)
int tag[maxn<<2];
void pushdown(int cur){
    if(tag[cur]!=0){
        if(tr[cur<<1]!=inf) tr[cur<<1]-=tag[cur];
        if(tr[cur<<1|1]!=inf) tr[cur<<1|1]-=tag[cur];
        tag[cur<<1]+=tag[cur];
        tag[cur<<1|1]+=tag[cur];
        tag[cur]=0;
    }
}
void pushup(int cur){
    tr[cur]=min(tr[cur<<1],tr[cur<<1|1]);
}
void change(int cur,int lt,int rt,int pos){
    if(lt==rt){
        cnt[lt]-=tag[cur]*now[lt];
        tag[cur]=0;
        tr[cur]=(now[lt]==0?inf:(cnt[lt]/now[lt]));
        return ;
    }
    int mid=(lt+rt)>>1;
    pushdown(cur);
    if(pos<=mid) change(cur<<1,lt,mid,pos);
    else change(cur<<1|1,mid+1,rt,pos);
    pushup(cur);
}
void del(){
    for(pair<int,int> x:d[top]) change(1,1,maxn-1,x.first);
    for(pair<int,int> x:d[top]) now[x.first]-=x.second;
    for(pair<int,int> x:d[top]) change(1,1,maxn-1,x.first);
    top--;
}
signed main(){
    freopen("secure.in","r",stdin);
    freopen("secure.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    for(int i=2;i<maxn;i++){
        int x=i;
        while(pri[x]!=0){
            int y=pri[x];
            int s=0;
            while(x%y==0) x/=y,s++;
            d[i].push_back(make_pair(y,s));
        }
        if(x!=1) d[i].push_back(make_pair(x,1));
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[1]++;
        b[a[i]+1]--;
    }
    for(int i=1;i<maxn;i++){
        b[i]+=b[i-1];
        for(pair<int,int> x:d[i]) cnt[x.first]+=b[i]*x.second;
    }
    for(int i=2;i<=top;i++){
        for(pair<int,int> x:d[i]) now[x.first]+=x.second;
    }
    for(int i=1;i<maxn;i++) change(1,1,maxn-1,i);
    while(top>1){
        while(top>1&&tr[1]<1) del();
        if(top<=1) break; 
        ans.push_back(make_pair(top,tr[1]));
        int t=tr[1];
        tr[1]-=t;
        tag[1]+=t;
        del();
    }
    cout<<ans.size()<<'\n';
    for(pair<int,int> x:ans) cout<<x.first<<' '<<x.second<<'\n';
    return 0;
}
/*
4
114 514 1919 810
*/
/*
5
6 7 8 9 10
*/