【洛谷1463】[POI2002] [HAOI2007] 反素数（打表）

点此看题面
大致题意：定义g(x)$g(x)$为正整数x$x$的约数个数，一个反质数x$x$满足对于任意一个i(0<i<x)$i(0<i<x)$，g(i)<g(x)$g(i)<g(x)$，给你一个正整数n$n$，请你求出不大于n$n$的最大的反质数。

---

一个截图说明一切

看到这张截图了吗？这张截图上很清楚地写着打表二字。
既然洛谷都承认它是一道打表题了，那何乐而不为呢？

---

简单而又粗暴：打表的艺术

正如洛谷上的任务说明中写着的，打表虽然很赖皮，而且基本都是非正解，但是这种办法能让我们在省选中拿到一些会超时或者会超空间的一些数据点。
因此，打表也是一门艺术，也是一个非常实用的技巧。
正如这道题中，我们可以写一个程序找到1∼2000000000$1\sim 2000000000$范围内的每一个反质数（经过思考就可以想到其实并不多），然后打一个表，对于读入的n$n$，找到第一个大于n$n$的反质数ansi$an{s}_i$，然后输出ansi−1$an{s}_{i-1}$即可。
这真的是非常简单粗暴。
所以就不多说了，直接上代码。

---

代码

#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)
#define pc(ch) (pp_<100000?pp[pp_++]=(ch):(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=(ch)))
int pp_;char ff[100000],*A=ff,*B=ff,pp[100000];
using namespace std;
const int ans[100]={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,2000000001};
int n;
inline void read(int &x)
{
    x=0;static char ch;
    while(!isdigit(ch=tc()));
    while(x=(x<<3)+(x<<1)+ch-48,isdigit(ch=tc()));
}
inline void write(int x)
{
    if(x>9) write(x/10);
    pc(x%10+'0');
}
int main()
{
    register int i;
    for(read(n),i=1;;++i) if(ans[i]>n) return write(ans[i-1]),fwrite(pp,1,pp_,stdout),0;//找到第一个大于n的反质数ans[i]，然后输出ans[i-1]即可
    return 0;
}