题目分析本题要求给定若干个区间[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的质因数分解式为np1a1⋅p2a2⋯pkak n p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}np1a1⋅p2a2⋯pkak则nnn的正因数个数为d(n)(a11)(a21)⋯(ak1) d(n) (a_11)(a_21)\cdots(a_k1)d(n)(a11)(a21)⋯(ak1)因此要求一个数的因数个数只需要得到它的质因数分解形式然后对每个指数加111后连乘即可。预处理素数表由于U⩽108U \leqslant 10^8U⩽108U≈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记录每个质因数的指数最后计算(指数11)×(指数21)×⋯(指数_11) \times (指数_21) \times \cdots(指数11)×(指数21)×⋯。这种方法只关心因数个数而不关心具体是哪些因数效率更高。代码最终使用的是第二种方法调用getCountOfDivisors2\texttt{getCountOfDivisors2}getCountOfDivisors2因为本题只需要因数个数进行比较无需枚举因数。特殊情况处理当n1n1n1时因数只有111本身返回111。当nnn是素数时因数只有111和nnn返回222。利用预处理好的素数表isPrime可以快速判断。在质因数分解后若n1n1n1剩余说明剩余部分是一个大于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(nloglogn)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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintprimes;// 存储筛法得到的素数intisPrime[31263];// 标记是否为素数的数组intN,L,U;// 埃拉托色尼筛法筛选出 31263 以内的所有素数voidsieve(){memset(isPrime,1,sizeof(isPrime));// 初始化所有数为素数for(inti2;i31263;i)if(isPrime[i]){// 将 i 的倍数标记为非素数for(intj2*i;j31263;ji)isPrime[j]0;primes.push_back(i);// 将素数存入向量}}// 方法一通过生成所有因数来计算因数个数本题实际未使用intgetCountOfDivisors1(intn){if(n1)return1;// 1 的因数只有自身if(n31263isPrime[n])return2;// 素数有 2 个因数setintnumbers,divisors;numbers.insert(1);// 初始因数集合包含 1for(inti0;iprimes.size();i){while(n%primes[i]0){n/primes[i];if(numbers.size()){// 将现有因数乘以当前质因子生成新因数for(autoitnumbers.begin();it!numbers.end();it){divisors.insert(*it);divisors.insert(*it*primes[i]);}numbers.clear();}else{for(autoitdivisors.begin();it!divisors.end();it){numbers.insert(*it);numbers.insert(*it*primes[i]);}divisors.clear();}}if(n1)break;// 分解完成}// 如果剩余 n 1说明还有一个大于 31263 的素因子if(n1)return2;// 返回两个集合中较大的那个即所有因数的数量returnmax(numbers.size(),divisors.size());}// 方法二利用质因数分解和因数个数定理效率更高实际使用的方法intgetCountOfDivisors2(intn){if(n1)return1;// 1 的因数只有自身if(n31263isPrime[n])return2;// 素数有 2 个因数mapint,intdivisors;// 记录质因子及其指数// 用预处理好的素数进行质因数分解for(inti0;iprimes.size();i){while(n%primes[i]0){n/primes[i];divisors[primes[i]];// 指数加 1}if(n1)break;}// 如果 n 1说明剩余部分是一个大于 31263 的素数if(n1)return2;// 根据因数个数定理(a11)*(a21)*...intcount1;for(autopair:divisors)count*(pair.second1);returncount;}// 在给定区间 [L, U] 内查找因数个数最多的数voidfindNumber(){intminNL,maxCountOfDivisors0,countOfDivisors;// 遍历区间内的每一个数for(intiL;iU;i)if((countOfDivisorsgetCountOfDivisors2(i))maxCountOfDivisors){maxCountOfDivisorscountOfDivisors;minNi;// 更新为当前因数个数更多的数由于遍历是从小到大相同个数时自然保留较小的}// 按要求格式输出结果coutBetween L and ;coutU, minN has a maximum of ;coutmaxCountOfDivisors divisors.\n;}intmain(intargc,char*argv[]){// 加速输入输出cin.tie(0),cout.tie(0),cin.sync_with_stdio(false);sieve();// 预处理素数表cinN;// 读入区间个数while(N--){cinLU;findNumber();}return0;}
UVa 294 Divisors
题目分析本题要求给定若干个区间[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的质因数分解式为np1a1⋅p2a2⋯pkak n p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}np1a1⋅p2a2⋯pkak则nnn的正因数个数为d(n)(a11)(a21)⋯(ak1) d(n) (a_11)(a_21)\cdots(a_k1)d(n)(a11)(a21)⋯(ak1)因此要求一个数的因数个数只需要得到它的质因数分解形式然后对每个指数加111后连乘即可。预处理素数表由于U⩽108U \leqslant 10^8U⩽108U≈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记录每个质因数的指数最后计算(指数11)×(指数21)×⋯(指数_11) \times (指数_21) \times \cdots(指数11)×(指数21)×⋯。这种方法只关心因数个数而不关心具体是哪些因数效率更高。代码最终使用的是第二种方法调用getCountOfDivisors2\texttt{getCountOfDivisors2}getCountOfDivisors2因为本题只需要因数个数进行比较无需枚举因数。特殊情况处理当n1n1n1时因数只有111本身返回111。当nnn是素数时因数只有111和nnn返回222。利用预处理好的素数表isPrime可以快速判断。在质因数分解后若n1n1n1剩余说明剩余部分是一个大于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(nloglogn)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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintprimes;// 存储筛法得到的素数intisPrime[31263];// 标记是否为素数的数组intN,L,U;// 埃拉托色尼筛法筛选出 31263 以内的所有素数voidsieve(){memset(isPrime,1,sizeof(isPrime));// 初始化所有数为素数for(inti2;i31263;i)if(isPrime[i]){// 将 i 的倍数标记为非素数for(intj2*i;j31263;ji)isPrime[j]0;primes.push_back(i);// 将素数存入向量}}// 方法一通过生成所有因数来计算因数个数本题实际未使用intgetCountOfDivisors1(intn){if(n1)return1;// 1 的因数只有自身if(n31263isPrime[n])return2;// 素数有 2 个因数setintnumbers,divisors;numbers.insert(1);// 初始因数集合包含 1for(inti0;iprimes.size();i){while(n%primes[i]0){n/primes[i];if(numbers.size()){// 将现有因数乘以当前质因子生成新因数for(autoitnumbers.begin();it!numbers.end();it){divisors.insert(*it);divisors.insert(*it*primes[i]);}numbers.clear();}else{for(autoitdivisors.begin();it!divisors.end();it){numbers.insert(*it);numbers.insert(*it*primes[i]);}divisors.clear();}}if(n1)break;// 分解完成}// 如果剩余 n 1说明还有一个大于 31263 的素因子if(n1)return2;// 返回两个集合中较大的那个即所有因数的数量returnmax(numbers.size(),divisors.size());}// 方法二利用质因数分解和因数个数定理效率更高实际使用的方法intgetCountOfDivisors2(intn){if(n1)return1;// 1 的因数只有自身if(n31263isPrime[n])return2;// 素数有 2 个因数mapint,intdivisors;// 记录质因子及其指数// 用预处理好的素数进行质因数分解for(inti0;iprimes.size();i){while(n%primes[i]0){n/primes[i];divisors[primes[i]];// 指数加 1}if(n1)break;}// 如果 n 1说明剩余部分是一个大于 31263 的素数if(n1)return2;// 根据因数个数定理(a11)*(a21)*...intcount1;for(autopair:divisors)count*(pair.second1);returncount;}// 在给定区间 [L, U] 内查找因数个数最多的数voidfindNumber(){intminNL,maxCountOfDivisors0,countOfDivisors;// 遍历区间内的每一个数for(intiL;iU;i)if((countOfDivisorsgetCountOfDivisors2(i))maxCountOfDivisors){maxCountOfDivisorscountOfDivisors;minNi;// 更新为当前因数个数更多的数由于遍历是从小到大相同个数时自然保留较小的}// 按要求格式输出结果coutBetween L and ;coutU, minN has a maximum of ;coutmaxCountOfDivisors divisors.\n;}intmain(intargc,char*argv[]){// 加速输入输出cin.tie(0),cout.tie(0),cin.sync_with_stdio(false);sieve();// 预处理素数表cinN;// 读入区间个数while(N--){cinLU;findNumber();}return0;}
