警示后人
查看原帖
警示后人
538609
Neutralized楼主2022/5/7 16:04

扩展欧拉定理有一个适用条件:
bφ(p)b \ge \varphi(p)
这里展开计算 ccccc^{c^{c^{c^{\dots}}}} 时,应当在 solve 函数返回值处判断这个条件
由于返回值需要对 φx(p)\varphi^x(p) 取模,快速幂的过程是提前取了模的,不能算完快速幂后再判断,应当预处理每个 logcφx(p)\lfloor \log_c \varphi^x(p) \rfloor ,并对快速幂传入的指数进行判断

e.g.:

int t=solve(cnt-1,id-1,val);
return fstpow(id,t,mod)+(t>=Log[id]?mod:0);
2022/5/7 16:04
加载中...