题解 P1463 【[SDOI2005]反素数ant】

· · 题解

如果你很聪明的话一分钟就可以打出来一个表

#include<bits/stdc++.h>
using namespace std;
int p[500]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360,2001000000};
int main()
{
    int n;
    freopen("ant.in","r",stdin);
    freopen("ant.out","w",stdout);
    cin>>n;
    int ans;
    for(int i=0;;i++)
    {
        if(p[i]>n) {
            cout<<p[i-1]<<endl;
            return 0;
        }
    }
}

打表的过程就是数字较大时会发现都是某个数的倍数，然后就只枚举这个数的倍数暴力判断，一段一段打。最后一个数是用来卡边界的。freopen什么的不要在意吧。

咳咳咳 我来补一个正确的做法。

首先这类数其实叫highly composite number（高合成数）,在51nod上有该题的加强版，数据范围给到了10^200。在讨论区一位dalao给出一个高合成数一定是由另一个高合成数乘一个素数得来的结论。并且我们发现这类数分解质因数，随质因数增大，指数显然单调不增（贪心）。 对于一个高合成数一定是由另一个高合成数乘一个素数得来这个结论可以这样感性理解。比如已经得到一个高合成数n=2^{k_1}*3^{k_2}*...，那么想找到比这个数约数个数多的最小的数是2n，它的约数个数是n的\frac{k_1+2}{k_1+1}，我们可以继续重复这个过程，但是到某一刻会发现乘多个2和乘一个其他的素数得到的数约数个数相同（例如乘k_1+1个2和乘一个指数为0的最小质数），但却比那个数数值更大，那么显然可以乘那个质数。大家可以结合wiki上的example给出的表格观察一下。 我们可以使用priority_queue，把1放进去，然后按随质因数增大指数单调不增的性质来入队新的数。