题解 | #小红的区间选数乘积#

题目链接

题目描述

给定 $q$ 次询问，每次询问给出三个正整数 $x, l, r$ 。需要找到在区间 $[l, r]$ 中有多少个正整数 $y$ ，满足 $x \cdot y$ 是一个完全平方数。数据范围为 $1 \le x, l, r \le 10^{14}$ 。

解题思路

一个数是完全平方数，当且仅当其所有质因子的指数都是偶数。为了让 $x \cdot y$ 成为完全平方数， $y$ 的作用就是“补全” $x$ 中那些指数为奇数的质因子。

1. 核心思想：平方剩余部分

我们可以将任意正整数 $x$ 分解为 $x = s \cdot m^2$ 的形式，其中 $s$ 是一个“无平方因子数”（Square-Free Number），即 $s$ 的所有质因子指数都为1。这个 $s$ 就是 $x$ 的“平方剩余部分”。

要使 $x \cdot y = (s \cdot m^2) \cdot y$ 成为完全平方数， $y$ 必须具有 $y = s \cdot p^2$ 的形式，其中 $p$ 是任意正整数。这样 $x \cdot y = s^2 \cdot m^2 \cdot p^2 = (s \cdot m \cdot p)^2$ ，满足条件。

因此，问题转化成了：计算在区间 $[l, r]$ 中，有多少个形如 $s \cdot p^2$ 的数，其中 $s$ 是 $x$ 的平方剩余部分。

2. 挑战：大数质因数分解

由于 $x$ 的范围高达 $10^{14}$ ，传统的试除法分解质因数（复杂度 $O(\sqrt{x})$ ）会超时。我们需要更高级的算法来处理大数的分解。

Miller-Rabin 素性检验：一个高效的、确定性的（在 long long 范围内）素数判断算法。
Pollard's Rho 算法：一个高效的随机整数分解算法，期望复杂度为 $O(n^{1/4})$ ，能快速找到一个大合数的因子。

通过结合这两种算法，我们可以为高达 $10^{14}$ 的数字 $x$ 高效地找到其所有质因子，从而计算出它的平方剩余部分 $s$ 。

3. 计算 $s$ 的流程

使用我们高效的分解算法，得到 $x$ 的所有质因子及其对应的指数，存入一个 map 中。
遍历这个 map，将所有指数为奇数的质因子累乘起来，得到的结果就是 $s$ 。

4. 计数

得到 $s$ 后，问题变为寻找有多少个正整数 $p$ 满足： $l \le s \cdot p^2 \le r$

变形得到： $\sqrt{\frac{l}{s}} \le p \le \sqrt{\frac{r}{s}}$

由于 $p$ 是整数，所以 $p$ 的最小取值是 $\lceil\sqrt{\frac{l}{s}}\rceil$ ，最大取值是 $\lfloor\sqrt{\frac{r}{s}}\rfloor$ 。但为了避免浮点数精度问题，我们可以这样计算：

$p$ 的下界对应的 $p^2$ 的下界是 $\lceil l/s \rceil$ 。第一个满足条件的 $p$ 是 $\lceil\sqrt{\lceil l/s \rceil}\rceil$ 。这等价于 (long long)sqrt((l-1)/s) + 1。
$p$ 的上界是 (long long)sqrt(r/s)。最终，总数是 sqrt(r / s) - sqrt((l - 1) / s)。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <map>
#include <algorithm>

using namespace std;
using ull = unsigned long long;
using ll = long long;

// 使用 __int128 进行大数乘法，防止溢出
ll power(ll base, ll exp, ll mod) {
    ll res = 1;
    __int128 b = base;
    b %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = ((__int128)res * b) % mod;
        b = (b * b) % mod;
        exp /= 2;
    }
    return res;
}

// Miller-Rabin 素性检验
bool check_composite(ll n, ll a, ll d, int s) {
    __int128 x = power(a, d, n);
    if (x == 1 || x == n - 1) return false;
    for (int r = 1; r < s; r++) {
        x = (x * x) % n;
        if (x == n - 1) return false;
    }
    return true;
}

bool MillerRabin(ll n) {
    if (n < 2) return false;
    int s = 0;
    ll d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    // 针对 64位整数 的确定性测试基数
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a) return true;
        if (check_composite(n, a, d, s)) return false;
    }
    return true;
}

// 修复后的 Pollard's Rho 算法
ll pollard(ll n) {
    if (n % 2 == 0) return 2;
    if (MillerRabin(n)) return n;
    
    auto f = [&](__int128 x, ll c) {
        return (x * x + c) % n;
    };
    
    ll x = 2, y = 2, d = 1, c = 1;
    while (true) {
        x = 2; y = 2; d = 1;
        while (d == 1) {
            x = f(x, c);
            y = f(f(y, c), c);
            d = std::gcd(abs(x - y), n);
        }
        if (d != n) return d;
        c++; // 失败，尝试下一个c
    }
}

map<ll, int> factors;
void factorize(ll n) {
    if (n <= 1) return;
    if (MillerRabin(n)) {
        factors[n]++;
        return;
    }
    ll p = pollard(n);
    factorize(p);
    factorize(n / p);
}


ll get_square_free(ll n) {
    factors.clear();
    factorize(n);
    ll s = 1;
    for (auto const& [p, count] : factors) {
        if (count % 2 != 0) {
            s *= p;
        }
    }
    return s;
}

// 精确的整数平方根
ull isqrt(ull n) {
    if (n < 2) return n;
    ull root = sqrt(n);
    // 使用__int128防止检查时溢出
    while ((__int128)(root + 1) * (root + 1) <= n) {
        root++;
    }
    while ((__int128)root * root > n) {
        root--;
    }
    return root;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        ll x, l, r;
        cin >> x >> l >> r;
        ll s = get_square_free(x);
        
        ull upper_r = r / s;
        ull lower_l = (l - 1) / s;

        ull count_upper = isqrt(upper_r);
        ull count_lower = isqrt(lower_l);
        
        cout << count_upper - count_lower << "\n";
    }
    return 0;
}

import java.math.BigInteger;
import java.util.*;

public class Main {
    // Miller-Rabin素性检验
    public static boolean isPrime(long n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        // BigInteger自带的概率性素性测试，确定性很高
        return BigInteger.valueOf(n).isProbablePrime(20);
    }

    // Pollard's Rho 算法
    private static long pollard(long n) {
        if (n % 2 == 0) return 2;
        if (isPrime(n)) return n;
        
        BigInteger N = BigInteger.valueOf(n);
        BigInteger x = new BigInteger(Long.toString(System.nanoTime() % (n-2) + 2));
        BigInteger y = x;
        BigInteger c = new BigInteger(Long.toString(System.nanoTime() % n + 1));
        BigInteger d = BigInteger.ONE;

        while (d.equals(BigInteger.ONE)) {
            x = x.multiply(x).add(c).mod(N);
            y = y.multiply(y).add(c).mod(N);
            y = y.multiply(y).add(c).mod(N);
            d = x.subtract(y).abs().gcd(N);
        }
        if (d.equals(N)) return pollard(n); // 失败，重试
        return d.longValue();
    }
    
    static Map<Long, Integer> factors = new HashMap<>();
    
    private static void factorize(long n) {
        if (n <= 1) return;
        if (isPrime(n)) {
            factors.put(n, factors.getOrDefault(n, 0) + 1);
            return;
        }
        long p = pollard(n);
        factorize(p);
        factorize(n / p);
    }

    public static long get_square_free(long n) {
        factors.clear();
        factorize(n);
        long s = 1;
        for (Map.Entry<Long, Integer> entry : factors.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                s *= entry.getKey();
            }
        }
        return s;
    }
    
    // 整数开方
    public static long isqrt(long n) {
        if (n < 0) return 0;
        long root = (long)Math.sqrt(n);
        while (BigInteger.valueOf(root + 1).multiply(BigInteger.valueOf(root + 1)).compareTo(BigInteger.valueOf(n)) <= 0) {
            root++;
        }
        while (BigInteger.valueOf(root).multiply(BigInteger.valueOf(root)).compareTo(BigInteger.valueOf(n)) > 0) {
            root--;
        }
        return root;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long x = sc.nextLong();
            long l = sc.nextLong();
            long r = sc.nextLong();
            
            long s = get_square_free(x);
            
            long upper_r = r / s;
            long lower_l = (l - 1) / s;
            
            long count_upper = isqrt(upper_r);
            long count_lower = isqrt(lower_l);
            
            System.out.println(count_upper - count_lower);
        }
    }
}

import math
import random

# Miller-Rabin 素性检验
def is_prime(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # 针对 64位整数 的确定性测试基数
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in bases:
        if n == a:
            return True
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# Pollard's Rho 算法
def pollard(n):
    if n % 2 == 0:
        return 2
    if is_prime(n):
        return n
    
    c = random.randint(1, n - 1)
    x = random.randint(0, n - 1)
    y = x
    d = 1
    
    while d == 1:
        x = (pow(x, 2, n) + c) % n
        y = (pow(y, 2, n) + c) % n
        y = (pow(y, 2, n) + c) % n
        d = math.gcd(abs(x - y), n)
        if d == n:
            return pollard(n) # 失败，重试
    return d

factors = {}
def factorize(n):
    if n <= 1:
        return
    if is_prime(n):
        factors[n] = factors.get(n, 0) + 1
        return
    p = pollard(n)
    factorize(p)
    factorize(n // p)

def get_square_free(n):
    global factors
    factors = {}
    factorize(n)
    s = 1
    for p, count in factors.items():
        if count % 2 != 0:
            s *= p
    return s

# 整数开方
def isqrt(n):
    if n < 0: return 0
    x = int(math.sqrt(n))
    if (x + 1) * (x + 1) <= n:
        x += 1
    return x

def solve():
    x, l, r = map(int, input().split())
    s = get_square_free(x)
    
    upper_r = r // s
    lower_l = (l - 1) // s
    
    count_upper = isqrt(upper_r)
    count_lower = isqrt(lower_l)
    
    print(count_upper - count_lower)

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：数论、Pollard's Rho、Miller-Rabin
时间复杂度：对于每次查询，主要开销在于分解质因数。Pollard's Rho 算法的期望时间复杂度为 $O(N^{1/4} \log N)$ ，其中 $N$ 是待分解的数。总时间复杂度约为 $O(q \cdot x_{max}^{1/4} \log x_{max})$ ，其中 $q$ 是查询次数。这对于本题的数据范围来说是足够高效的。
空间复杂度：递归分解质因数时，递归深度和存储质因子的 map 大小都与 $\log x$ 相关，因此空间复杂度为 $O(\log x)$ 。