数论与位运算·单选训练1

第 1 题（单选）

若需要计算 a*b%mod 且 a,b 可接近 1e18，最稳妥的常见方法是（）。

{{ select(1) }}

• 使用 __int128 或快速乘
• 转成 int
• 先除以 mod
• 直接 long long 相乘

第 2 题（单选）

模质数 p 下直接用 fac[n] 与 invfac[n] 预处理组合数 C(n,k)，且要求 fac[n] 可逆，通常需要（）。

{{ select(2) }}

• n 为质数
• k=0
• n<p
• p<n

第 3 题（单选）

埃氏筛中，当 i 已知为质数时，从 i*i 开始标记其倍数的主要原因是（）。

{{ select(3) }}

• i*i 以前的倍数一定也是质数
• 更小的合数倍数已被更小质因子标记
• 只有平方数才是合数
• 可以把空间复杂度降为 O(1)

第 4 题（单选）

用 2×2 矩阵快速幂计算第 n 项斐波那契数，乘法视为 O(1) 时，时间复杂度为（）。

{{ select(4) }}

• O(log n)
• O(n)
• O(n log n)
• O(2^n)

第 5 题（单选）

表达式 1LL << 40 的类型和意图通常是（）。

{{ select(5) }}

• long long，表示 2^40
• bool，表示 true
• int，可能溢出
• double，表示 40