题解：P14640 【OIMO Round 1】校验

· · 题解

P14640 【OIMO Round 1】校验

题目大意

  1. 正整数 x 的校验值： (-1)^{\Omega(x)}（\Omega(x) 表示 x 的可重素因子个数，例如 \Omega(12)=\Omega(2×2×3)=3，校验值为 -1）；
  2. 数 n 的喜爱度：n 所有因数的校验值之和，即 f(n) = \sum\limits_{d\mid n} (-1)^{\Omega(d)}；
  3. 问题要求：给定 T 组查询区间 [l,r]，求区间内所有数的喜爱度之和 \sum\limits_{i=l}^r f(i)。

基本思路

核心是简化 f(n) 的计算规则，最终将问题转化为统计完全平方数个数：

  1. 对 n 素因数分解 n = p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}，其因数 d = p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}（0\le a_i\le k_i）；
  2. 校验值满足乘积性：(-1)^{\Omega(d)} = \prod\limits_{i=1}^m (-1)^{a_i}，因此 f(n) = \prod\limits_{i=1}^m \sum\limits_{a_i=0}^{k_i} (-1)^{a_i}；
  3. 单素因子项求和：\sum\limits_{a=0}^k (-1)^a，若 k 为偶数则和为 1，若 k 为奇数则和为 0；
  4. 最终结论：f(n)=1 当且仅当 n 是完全平方数（所有素因子指数为偶数），否则 f(n)=0。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll int_sqrt(ll x) {
    if (x < 0) return 0;
    ll k = ll(sqrtl(x)); 
    while ((k + 1) * (k + 1) <= x) k++;
    while (k * k > x) k--;
    return k;
}
int T;
ll l, r;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> l >> r;
        ll cnt_r = int_sqrt(r);
        ll cnt_l_1 = int_sqrt(l - 1);
        cout << (cnt_r - cnt_l_1) << '\n';
    }
    return 0;
}