UVA294 约数 Divisors

· · 题解

Content

给定 n 个区间 [l,r]，求出每个区间内约数个数最大的数。

数据范围：1\leqslant l<r\leqslant 10^{10}，r-l\leqslant 10^4。

Solution

你可能需要在做这题目前了解一下约数个数定理。何谓约数个数定理？

设一个数 x 的个数可以分解为若干个质因数相乘的积，即：

x=\prod\limits_{i=1}^k p_i^{a_i}

那么 x 的约数个数 f(x) 有一个这样的式子：

f(x)=\prod\limits_{i=1}^k(a_i+1)

如何证明？很简单，我们由约数定义可知，p_1^{a_1} 的约数有：p_1^0,p_1^1, p_1^2,\dots,p_1^{a_1}，共 a_1+1 个。同理 p_2^{a_2} 的约数有 a_2+1 个……以此类推，p_k^{a_k} 的约数有 a_k+1 个。因此，由乘法原理可知，x 的约数个数就是 (a_1+1)(a_2+1)\dots(a_k+1)=\prod\limits_{i=1}^k(a_i+1)。

那么思路就非常清晰明了了：

  1. 预处理出 \sqrt{10^{10}} 以内的所有质数，可以用埃氏筛也可以用线性筛。
  2. 注意到 r-l\leqslant 10^4，因此我们考虑直接从 l 到 r 枚举每一个数。
  3. 枚举每一个数时，我们枚举每一个质数，一旦发现这个质数是当前枚举到的数的因子，我们就不断地将当前枚举的数除以这个质因子，直到这个质数不再是当前述的因子为止。
  4. 设我们除了 num 次，然后我们往当前枚举的数的约数个数（初始化为 1）去乘 num+1。当前数的质因子分解完了以后再和当前的答案比较，并更新答案。

Code

namespace Solution {
    int cnt, isprime[100007], prime[100007];

    iv ai_prime() {
        F(int, i, 2, 100000) isprime[i] = 1;
        F(int, i, 2, 100000) if(isprime[i]) Fo(int, j, i * 2, 100000, i) isprime[j] = 0;
        F(int, i, 2, 100000) if(isprime[i]) prime[++cnt] = i;
    }

    iv Main() {
        ai_prime();
        MT {
            ll l = Rll, r = Rll, ans = 0, res = l;
            F(ll, i, l, r) {
                ll p = i, num = 1;
                for(int j = 1; j <= cnt && prime[j] <= p; ++j) {
                    ll t = 0;
                    while(prime[j] && !(p % prime[j])) p /= prime[j], t++;
                    num *= (t + 1);
                }
                if(num > ans) res = i, ans = num;
            }
            printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n", l, r, res, ans);
        } 
        return;
    }
}