CF1114F 题解：把欧拉函数拆成两半来维护

题目链接。数组支持区间乘 $x$，查询一段乘积的欧拉函数，答案模 $M=10^9+7$。

一般情况下，$\varphi(ab)\ne\varphi(a)\varphi(b)$。把公式拆开，才能找到可合并的信息。

乘积记数值，质因子只记有没有

设区间真实乘积为 $P$，不同质因子的集合为 $S$，则

保存 $P\bmod M$ 和取模前的质因子集合。同一个质数的修正系数只乘一次：

初始值和乘数都不超过 $300$，可能出现的质数只有 $62$ 个，一个 uint64_t 就能保存集合。

合并时乘积相乘、掩码取或。不能重新分解取模后的乘积来恢复集合。

整段乘 x 时，两个部分分别怎样变

如果区间长度为 $L$，每个元素都乘 $x$，那么区间乘积需要乘 $x^L$，集合则并入 $x$ 的所有质因子。所以节点保存 (product, mask, length)，懒标记保存 (multiplier, mask)。

两个懒标记合并：乘数相乘，集合取或。这里没有赋值，操作顺序也不影响结果。

查询得到节点后，枚举掩码中存在的质数，补乘 $(p-1)\cdot p^{-1}\bmod M$。这里每个 $p<M$，与质数模数 $M$ 互质，逆元存在。

代码

下面只列节点操作；power 是普通的模快速幂。预处理出 62 个质数、每个 $x\le300$ 的掩码，以及每个质数的修正系数后，线段树递归部分就不再需要分解整数。

#include <cstdint>

using u64 = std::uint64_t;
const long long MOD = 1'000'000'007;
long long power(long long x, int e); // 模 MOD 的快速幂

struct Info {
    long long product = 1;
    u64 mask = 0;
    int length = 0;
};
struct Tag { long long multiplier = 1; u64 mask = 0; };

Info merge(Info a, Info b) {
    return {a.product * b.product % MOD,
            a.mask | b.mask, a.length + b.length};
}

void apply(Info& node, Tag tag) {
    node.product = node.product * power(tag.multiplier, node.length) % MOD;
    node.mask |= tag.mask;
}

Tag compose(Tag a, Tag b) {
    return {a.multiplier * b.multiplier % MOD, a.mask | b.mask};
}

位运算 a.mask | b.mask 一次就能合并整个集合，无需再循环 62 次。叶子用 (a_i, mask[a_i], 1) 初始化，空查询结果是 (1,0,0)，无修改标记是 (1,0)。

这份写法在每次节点更新时计算 $x^L$，因此一次区间修改上界为 $O(\log^2 n)$；查询加上枚举质因子的修正为 $O(\log n+62)$，空间 $O(n)$。位掩码把集合操作变得很便宜，但不会省掉快速幂的开销。