bzoj1053题解

【题意分析】

　　本题中，x被称为反质数，当且仅当没有任意一个严格小于x的正整数的约数个数大于x的约数个数。求不超过N的最大反质数。

【解题思路】

　　数据范围中最大的N=2*10⁹。

　　首先可以证明，不超过N的反质数不会拥有9个以上的不同质因数。因为2*3*5*7*11*13*17*19*23*29=6469693230>6*10⁹>N。

　　设某数n=∏p_i^k_i(p_i<p_i+1)，则其约数个数g(n)=∏(k_i+1)。（因为每个质数对约数个数的贡献是相互独立的，质数p_i的可能选择方案数为(k_i+1)，所以可以用乘法原理乘起来）。

　　显然，对于相同的顺序序列k，选择越小的p_i越优，于是最优选择方案就是选择前9个质因数。

　　于是暴力枚举的状态数为∏[log_pN]，则其至多为[log₂N]*[log₃N]*[log₅N]*[log₇N]*[log₁₁N]*[log₁₃N]*[log₁₇N]*[log₁₉N]*[log₂₃N]=3779758080。

　　显然直接暴力是无法过的，于是需要一些鲁（吉）棒（丽）或玄（松）学（爷）优化。

　　所谓鲁棒优化，就是打表。。先把所有的反质数用上面这个爆搜打出来存在表里，然后二分查找即可。

　　打表做法的可行性得益于反质数个数的增长极其缓慢，10⁵的数据范围中只有30个反质数，从下图不难看出。

　　玄学优化呢，有两种方法：

•方法一：考虑对k_i的枚举进行优化。一种朴素的想法是同一个素因数的个数过多一定不利于让答案最优，而且越大的质因数个数应当越少，于是可以面向数据调参，限制k_i枚举的上限。

•方法二：部分记忆化，f[i][j]表示j的乘积分配给第i个开始的质数最大能达到的约数个数，然后可以对超出记忆化范围的搜索做下界减枝。

　　复杂度O(松)。

【参考代码】

　　然而当时这题我只用了玄学优化方法一的弱化版，不知为什么就0ms过了？！

　　可能有更加紧确的复杂度分析或者bz的数据有毒。。无论是哪一点请读者指出，不胜感激。

 #include<cstdio>

 #define REP(I,start,end) for(int I=start;I<=end;I++)

 const int prime[]={,,,,,,,,,,,,,,,};

 long long maxsum, bestnum, n;

 void getantiprime(long long num, long long k,long long sum,int limit)

 {

     int i;

     long long temp;

     if(sum>maxsum)

     {

         maxsum=sum;

         bestnum=num;

     }

     if(sum==maxsum&&bestnum>num)

     bestnum=num;

     if(k>)

         return;

     temp=num;

     REP(i,,limit)

     {

         if(temp*prime[k]>n)

             break;

         temp*=prime[k];

         getantiprime(temp,k+,sum*(i+),i);

     }

 }

 int main()

 {

     scanf("%lld",&n);

     getantiprime(,,,);

     printf("%lld\n",bestnum);

     return ;

 }

巴特西

bzoj1053题解

最新文章

热门文章