考点：数论

数据规模 T ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：T ≤ 1e5
• 元素值域：x ≤ 1e9（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：数论

本题切入点

关键结论：x 存在偶数因子当且仅当 x 本身是偶数（2 就是偶数因子；x 为奇数时所有因子必为奇数）。T≤1e5、x≤1e9 必须用这个 O(1) 结论，逐个分解因子必超时。

围绕整除、质因数、同余的经典结论与筛法。

思路框架（数论 通法 · 非本题专属）

1. 先做质因数分解（试除到 √n，或预处理筛出 1e6 内质数）。
2. 按题意套结论：约数个数 = Π(e_i+1)；gcd / lcm 用辗转相除法。
3. 涉及大数取模时，每一步运算后都取模，避免溢出。
4. 需要区间内质数时用埃氏筛 / 线性筛。

实现要点：模运算规律：(a+b)%m = ((a%m)+(b%m))%m，乘法则同理；减法要 +m 防止负数。

复杂度：时间 O(√n) 分解 / O(n log log n) 筛 ｜ 空间 O(n) 筛表

该范式的通法易错点

• 取模后相减为负数没处理。
• a*b 在取模前就溢出了。

对照本题

• 数据规模 T ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 / 1 / 4 → 输出 NO / YES

1 不存在偶数因子， 4 存在偶数因子 2 。