题解 P1463 【[POI2002][HAOI2007]反素数】

· · 题解

此题同样是打表，但我们有特殊的打表方法

首先我们可以打个暴力找一下规律，即下面代码中被注释掉的部分，

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n,i,j,a,maxn=0,num,last;
    cin>>n;
    i=2;
    if(n>=61261200)
     i=61261200;
    for(;i<=n;)
     {
        a=i;
        num=0;
        for(j=2;j<=sqrt(i);j++)
         {
            if(i%j==0)
              num+=2;
            if(j*j==i)
             num-=1;
         }
        if(num>maxn)
        {
            maxn=num;
            last=i;
            a=i;
            /*cout<<i<<" ";
            for(j=2;j<=a;j++)
             {
                if(a%j==0)
                 {
                    cout<<j<<" ";
                    a/=j;
                    j--;
                 }
             }
            cout<<endl;*/
        } 
        if(i>=61261200)
         i+=510510;
        if(i>=720720&&i<61261200)
         i+=30030;
        if(i>=55440&&i<720720)
         i+=2310;
        if(i>=840&&i<55440)
         i+=210;    
        if(i>=180&&i<840)
          i+=30;
        if(i>=24&&i<180)
          i+=6;
        if(i<24)
          i++;
     }
     cout<<last;
     return 0;
}

大家都知道如果每次i++就是nlogn的暴力，但通过打表我们找到了什么规律呢？

我们可以看到，当i不小于24时，所有的反质数都含有因子2,3

i不小于180时，所有的反质数都含有因子2，3，5

i不小于840时，所有的反质数都含有因子2,3,5,7

以此类推，这样的话我们每次就可以不用i++，而是i+=a，由于越往后a越大，时间复杂度就会很小

同时，当n很大时，我们可以从一个已知的比较大的反质数开始找，这样就可以940ms卡过第二个点