首页 > 代码库 > URAL 1748. The Most Complex Number（反素数）
URAL 1748. The Most Complex Number（反素数）
题目链接
题意 ：给你一个n，让你找出小于等于n的数中因子个数最多的那个数，并且输出因子个数，如果有多个答案，输出数最小的那个
思路 ： 官方题解 ：
（1）此题最容易想到的是穷举，但是肯定超时。
（2）我们可以知道，计算约数的个数和质因数分解有着很大的联系： 若Q的质因数分解为：Q=p1^k1*p2^k2*…*pm^km（p1…pm为素数，k1…km≥1），则Q有(k1+1)(k2+1)…(km+1)个约数。但是质因数分解的时间复杂度很高，所以也会超时。
（3）通过以上的公式，我们可以“突发奇想”：为何不能把质因数分解的过程反过来呢？ 这个算法就是枚举每一个素数。初始时让m=1，然后从最小的素数2开始枚举，枚举因子中包含0个2、1个2、2个2…k个2，直至m*2^k大于区间的上限N。在这个基础上枚举3、5、7……的情况，算出现在已经得到的m的约数个数，同时与原有的记录进行比较和替换。直至所有的情况都被判定过了。 这个算法的优化：如果p1*p2*p3*……*pk>N（pi表示第i个素数），那么只要枚举到p k-1，既不浪费时间，也不会遗漏。
（4）以上的算法还不是最好的，还可以继续优化。 我们看以下的例子： 6=2*3 10=2*5 6和10的质因数分解“模式”完全相同，所以它们的约数个数是相同的。但是由于3<5，所以6<10。 12=2^2*3 18=3^2*2 12和18的质因数分解“模式”完全相同，所以它们的约数个数是相同的。但是由于12的质因数分解中2的指数大于3的指数，18的质因数分解中3的指数大于2的指数，所以12<18。 根据以上的举例，我们也可以对（3）中的算法进行一个改进：可以在枚举时进行一个优化，使得枚举到的数字中2的指数不小于3的指数，3的指数不小于5的指数……这样我们就能够得到质因数分解“模式”相同的最小数（证明略）。再对于每一个得到的数进行比较和记录。这个算法的优化力度极大，效率几乎达到了极限。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #define LL long long 5 using namespace std ; 6 7 LL n,minnum,cnt ; 8 const int prime[20] = {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47} ; 9 10 //num：当前枚举到的数，k：枚举到的第k大的质因子；cntt：该数的约数个数；maxxcnt：质因子个数上限；11 void dfs(LL num,LL k,LL cntt,int maxxcnt)12 {13 if(k >= 16) return ;14 15 //如果约数个数更多或者相同，将最优解更新为当前数；16 if(cntt > cnt || (cntt == cnt && num < minnum))17 {18 cnt = cntt ;19 minnum = num ;20 }21 LL temp = num ;22 for(LL i = 1 ; i <= maxxcnt ; i++) //开始枚举每个质因子的个数；23 {24 if(temp > n / prime[k])25 break ;26 temp *= prime[k] ; //累乘到当前数；27 dfs(temp,k+1,cntt*(i+1),i) ;28 }29 }30 int main()31 {32 int T ;33 scanf("%d",&T) ;34 while(T--)35 {36 scanf("%I64d",&n) ;37 minnum = cnt = 1 ;38 dfs(1,1,1,50) ;39 printf("%I64d %I64d\n",minnum,cnt) ;40 }41 return 0 ;42 }
反素数介绍
URAL 1748. The Most Complex Number（反素数）