CF396E On Iteration of One Well-Known Function [欧拉函数 III]

$O n <mtext> </mtext> I t e r a t i o n <mtext> </mtext> o f <mtext> </mtext> O n e <mtext> </mtext> W e l l - K n o w n <mtext> </mtext> F u n c t i o n$

$D e s c r i p t i o n$
给出 $n = \prod_{i = 1}^{m} p_{i}^{a_{i}}$ , 求 $φ (φ (. . . φ (n)))$ .

$m \leq 1 0^{5}, p_{i} \leq 1 0^{6}, a_{i} \leq 1 0^{17}, k \leq 1 0^{18} .$

$正解部分$
因为 $φ (n) = n \prod_{i = 1}^{m} \frac{p_{i} - 1}{p_{i}}$ ,
所以对一个整数 $x$ 进行一次 $φ$ 操作即 $↓$

乘一次 $\prod_{i = 1}^{m} \frac{1}{p_{i}}$ , 即 $p_{i}$ 项的幂数减 $1$ .
乘一次 $\prod_{i = 1}^{m} (p_{i} - 1)$ , 对 $p_{i} - 1$ 分解质因数, 使得对应的较小的质数的幂数增加若干.

那么怎么快速地去求解本题的式子呢?

从小到大共有 $1 0^{6}$ 个质数, 对每个质数单独处理,
设当前质数为 $p_{i}$ , 还需进行 $l e f t_{i}$ 次 $φ$ 操作, 指数为 $a_{i}$ ,

为保证效率最大化, 将 $p_{i}$ 进行 $t = m i n (a_{i}, l e f t_{i})$ 次 $φ$ 操作,
这样会使得 $(p_{i} - 1)^{t}$ 分解, “散落” 到比 $p_{i}$ 更小的质数中,
所以需要循环往复地对每个质数进行这个操作, 直到没有任何质数有操作的余地 .

对当前 $p_{i}$ , 若进行了 $t$ 次 $p h i$ 操作, 则需要在指数为 $0$ 时, $S O S_{i} = t - 1$ 次操作不去减 $l e f t_{i}$ , 因为可能还有指数不为 $0$ 的希望,
过了 $S O S_{i}$ 后若指数仍然为 $0$ , ~~表示没救了~~, 需要使 $l e f t_{i}$ 减小 .

$实现部分$
在质数筛时记录每个数 $x$ 的最小质因子 $c o m e [x]$ , 分解质因数时, 就可以利用 $c o m e [x]$ 直接分解 .

记得在开始时每个质数的 $l e f t$ 都为 $K$ , 因为每个质数都有可能参与运算 .

#include<cstdio>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 1e6+5;

int M;
int p_cnt;
int p[maxn];
int q[maxn];
int Mp[maxn];
int come[maxn];

ll K;
ll a[maxn];
ll SOS[maxn];
ll left[maxn];

void Sieve(){
        for(reg int i = 2; i < maxn; i ++){
                if(!come[i]) come[i] = i, p[++ p_cnt] = i, Mp[i] = p_cnt;
                for(reg int j = 1; j <= p_cnt && i*p[j] < maxn; j ++){
                        int t = i*p[j];
                        come[t] = p[j];
                        if(i % p[j] == 0) break ;
                }
        }
}

int main(){
        //freopen("a.out", "w", stdout);
        Sieve();
        scanf("%d", &M);
        for(reg int i = 1; i <= M; i ++){
                scanf("%d", &q[i]);
                scanf("%I64d", &a[Mp[q[i]]]);
        }
        scanf("%I64d", &K);
        for(reg int i = 1; i <= p_cnt; i ++) left[i] = K;
        bool flag = 1;
        while(flag){
                flag = 0;
                for(reg int i = 1; i <= p_cnt; i ++)
                        if(a[i]){ 
                                if(!left[i]) continue ;
                                ll t = std::min(a[i], left[i]);
                                a[i] -= t, left[i] -= t;
                                SOS[i] += t-1, flag = 1;
                                int tmp = p[i]-1;
                                while(tmp != 1){
                                        int id = Mp[come[tmp]];
                                        a[id] += t;
                                        tmp /= come[tmp];
                                }
                        }else if(SOS[i]) SOS[i] --;
                        else if(left[i])left[i] --;
        }
        int Ans = 0;
        for(reg int i = 1; i <= p_cnt; i ++) if(a[i]) Ans ++;
        printf("%d\n", Ans);
        for(reg int i = 1; i <= p_cnt; i ++)
                if(a[i]) printf("%d %I64d\n", p[i], a[i]);
        return 0;
}