当前位置：首页 > news >正文

UVa 294 Divisors

news 2026/6/1 22:10:27

题目分析

本题要求给定若干个区间[L,U][L, U][L,U]，在每个区间内找出一个数PPP，使得PPP的正因数个数DDD最大。如果有多个数因数个数相同且均为最大，则选取最小的那个数。最后按照指定格式输出结果。

题目给出的数据范围是1⩽L⩽U⩽1081 \leqslant L \leqslant U \leqslant 10^81⩽L⩽U⩽108，且区间长度满足0⩽U−L⩽100000 \leqslant U-L \leqslant 100000⩽U−L⩽10000。这意味着区间长度最大为10410^4104，但单个数字本身最大可达10810^8108。

一个最直接的想法是：对于区间内的每个数，通过试除法计算其因数个数，然后比较得出最大值。但10810^8108级别的数字，如果用n\sqrt{n}n的试除法（约为10410^4104次运算），再乘以区间长度10410^4104，总运算量约为10810^8108次，对于NNN个区间来说可能超时。因此需要更高效的算法。

解题思路

因数个数定理

根据数论知识，若一个正整数nnn的质因数分解式为：

n=p1a1⋅p2a2⋯pkak n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}n=p1a1⋅p2a2⋯pkak

则nnn的正因数个数为：

d(n)=(a1+1)(a2+1)⋯(ak+1) d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)d(n)=(a1+1)(a2+1)⋯(ak+1)

因此，要求一个数的因数个数，只需要得到它的质因数分解形式，然后对每个指数加111后连乘即可。

预处理素数表

由于U⩽108U \leqslant 10^8U⩽108，U≈10000\sqrt{U} \approx 10000U≈10000。实际上，316222≈10931622^2 \approx 10^9316222≈109，因此只需要筛出316223162231622以内的所有素数，即可对10810^8108以内的数进行质因数分解。

代码中取上界为312633126331263（稍大于316223162231622的近似值），使用埃拉托色尼筛法（Sieve\texttt{Sieve}Sieve）得到所有素数，存储在primes向量中。

计算因数个数的两种方法

代码中提供了两种计算因数个数的方法：

getCountOfDivisors1\texttt{getCountOfDivisors1}getCountOfDivisors1：通过集合交替存储因数。每次处理一个质因数时，将已有的因数集合中的每个数乘以该质因数，得到新的因数，然后交替存放在两个集合中。这种方法直接生成了所有因数，适用于需要实际因数的场景，但空间和时间开销较大。
getCountOfDivisors2\texttt{getCountOfDivisors2}getCountOfDivisors2：利用因数个数定理，先进行质因数分解，用map记录每个质因数的指数，最后计算(指数1+1)×(指数2+1)×⋯(指数_1+1) \times (指数_2+1) \times \cdots(指数1+1)×(指数2+1)×⋯。这种方法只关心因数个数而不关心具体是哪些因数，效率更高。

代码最终使用的是第二种方法（调用getCountOfDivisors2\texttt{getCountOfDivisors2}getCountOfDivisors2），因为本题只需要因数个数进行比较，无需枚举因数。

特殊情况处理

当n=1n=1n=1时，因数只有111本身，返回111。
当nnn是素数时，因数只有111和nnn，返回222。利用预处理好的素数表isPrime可以快速判断。
在质因数分解后，若n>1n>1n>1剩余，说明剩余部分是一个大于312633126331263的素数，此时因数个数需要再乘222。

主逻辑

对于每个区间[L,U][L, U][L,U]，遍历区间内的每一个数iii，调用getCountOfDivisors2(i)\texttt{getCountOfDivisors2}(i)getCountOfDivisors2(i)计算其因数个数，并与当前最大值比较。若遇到更大的因数个数，则更新最大值和对应的最小数字PPP。

由于区间长度最大仅为10410^4104，即使每个数的计算需要分解质因数（最多尝试108≈104\sqrt{10^8} \approx 10^4108≈104以内的素数），总计算量也是可接受的。

复杂度分析

预处理：筛法求素数的时间复杂度约为O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn)，其中n≈31622n \approx 31622n≈31622，非常快。
单次因数个数计算：最坏情况下需要遍历所有340134013401个素数（316223162231622以内的素数个数约为340134013401），每次除法运算很快。对于10810^8108附近的数，质因数分解很快结束。
整体：对于每个区间，最多计算100011000110001次因数个数，每次最多约340134013401次除法，总操作次数在3×1073 \times 10^73×107级别，实际运行非常迅速。

代码实现

// Divisors// UVa ID: 294// Verdict: Accepted// Submission Date: 2016-05-09// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>primes;// 存储筛法得到的素数intisPrime[31263];// 标记是否为素数的数组intN,L,U;// 埃拉托色尼筛法，筛选出 31263 以内的所有素数voidsieve(){memset(isPrime,1,sizeof(isPrime));// 初始化所有数为素数for(inti=2;i<31263;i++)if(isPrime[i]){// 将 i 的倍数标记为非素数for(intj=2*i;j<31263;j+=i)isPrime[j]=0;primes.push_back(i);// 将素数存入向量}}// 方法一：通过生成所有因数来计算因数个数（本题实际未使用）intgetCountOfDivisors1(intn){if(n==1)return1;// 1 的因数只有自身if(n<31263&&isPrime[n])return2;// 素数有 2 个因数set<int>numbers,divisors;numbers.insert(1);// 初始因数集合包含 1for(inti=0;i<primes.size();i++){while(n%primes[i]==0){n/=primes[i];if(numbers.size()){// 将现有因数乘以当前质因子，生成新因数for(autoit=numbers.begin();it!=numbers.end();it++){divisors.insert(*it);divisors.insert(*it*primes[i]);}numbers.clear();}else{for(autoit=divisors.begin();it!=divisors.end();it++){numbers.insert(*it);numbers.insert(*it*primes[i]);}divisors.clear();}}if(n==1)break;// 分解完成}// 如果剩余 n > 1，说明还有一个大于 31263 的素因子if(n>1)return2;// 返回两个集合中较大的那个（即所有因数的数量）returnmax(numbers.size(),divisors.size());}// 方法二：利用质因数分解和因数个数定理，效率更高（实际使用的方法）intgetCountOfDivisors2(intn){if(n==1)return1;// 1 的因数只有自身if(n<31263&&isPrime[n])return2;// 素数有 2 个因数map<int,int>divisors;// 记录质因子及其指数// 用预处理好的素数进行质因数分解for(inti=0;i<primes.size();i++){while(n%primes[i]==0){n/=primes[i];divisors[primes[i]]++;// 指数加 1}if(n==1)break;}// 如果 n > 1，说明剩余部分是一个大于 31263 的素数if(n>1)return2;// 根据因数个数定理：(a1+1)*(a2+1)*...intcount=1;for(autopair:divisors)count*=(pair.second+1);returncount;}// 在给定区间 [L, U] 内查找因数个数最多的数voidfindNumber(){intminN=L,maxCountOfDivisors=0,countOfDivisors;// 遍历区间内的每一个数for(inti=L;i<=U;i++)if((countOfDivisors=getCountOfDivisors2(i))>maxCountOfDivisors){maxCountOfDivisors=countOfDivisors;minN=i;// 更新为当前因数个数更多的数（由于遍历是从小到大，相同个数时自然保留较小的）}// 按要求格式输出结果cout<<"Between "<<L<<" and ";cout<<U<<", "<<minN<<" has a maximum of ";cout<<maxCountOfDivisors<<" divisors.\n";}intmain(intargc,char*argv[]){// 加速输入输出cin.tie(0),cout.tie(0),cin.sync_with_stdio(false);sieve();// 预处理素数表cin>>N;// 读入区间个数while(N--){cin>>L>>U;findNumber();}return0;}