P3747 [六省联考 2017] 相逢是问候

首先根据欧拉定理，每个位置最多操作 \(\log\) 次，然后维护一个模数为欧拉函数 \(p\) 的光速幂每次快速用线段树维护，即可做到两只 \(\log\) 了。