P1463 [POI2002][HAOI2007]反素数——题解
LYYY
2018-09-26 20:13:38
# 打表
我一开始是打算写正解的，但是看了看dalao们的题解，就扼杀了蒟蒻我写正解的想法，于是自己yy了一种打表
------------
------------
相信不会有比我还快用程序打的表了qwq（其实也不算纯打表，完全可以打表顺便AC）
------------
言归正传
1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260
先给出前几个反质数
我们可以发现相邻两个数之间的差值在近似地增大，为什么说近似呢，因为差值：
1,2,2,6,12,12,12,12,60,60,60,120,360,120,420
我们可以发现：360到720增了360，而720到840只增了120，所以大胆猜想：
**相邻两个反质数之间的差值会近似地单调递增，而且数字与差值之间存在一定倍数关系。**
所以我们在枚举（打表）时，不用一个一个地试，可以以之前的差值为单位增加，只尝试以这个差值为倍数的数，使时间复杂度会大大降低。而且合适的取值可以达到2e9内100%的正确率并时间允许。
### 详见代码：
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
int n,last,answer;
int chazhi[300];
//存储差值
int head=50,max_i=30;
//差值存储从50开始避免越界
//代码核心：因为差值并不是严格上升的，所以通过调用很早记下来的差值保证正确率（尽管会慢，但正确率会变高，用时间换正确率）
//ps:max_i的值可自定,2e9的范围100%正确率最小max_i为24，本代码用了30AC，不保险可以用40（但会很慢1min左右，可以先打表再做）
//函数名通俗易懂：求x约数个数
int geshu(int x){
int ans=1;
for(int i=2;i*i<=x;i++){
int tot=1;
while(x%i==0){
x/=i;
tot++;
}
ans*=tot;
}
if(x!=1)ans<<=1;
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=head;i++) chazhi[i]=1;
//初始化为1，先以1位单位增长
for(int i=1;i<=n;i+=chazhi[head-max_i]){
//核心：以往前数第max_i个差值(即chazhi[head-max_i])为单位增长
int lll=geshu(i);
if(lll>answer){
chazhi[++head]=i-last;
answer=lll;
last=i;
//更新并存储差值
printf("the %dth answer lower is:%d\n",head-50,last);
//该输出为打表
}
}
printf("%d",last);//答案
return 0;
}
```
附2e9内反质数表
```cpp
//共68个 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
```
_谢谢阅览_