时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
幽香今天心情不错，正在和花田里的虫子玩一个益智游戏。
这个游戏是这样的，对于一个数组A，幽香从A中选择一个数a，虫子从A中选择一个数b。a和b可以相同。她们的分数是a*b的因子的个数。
幽香和虫子当然想要获得尽可能的高的分数，你能告诉她们应该选择哪两个数吗。
由于幽香是个非常随意的人，数组A中的元素都是她随机选择的。
输入
一行一个数n，表示A中整数的数量。
接下来一行n个数，分别表示a1,a2,...,an，为A中的元素。
n <= 100000, 1 <= ai <= 100000
保证所有的ai都是随机生成的。
输出
一行表示最大的分数。
怎么想都没有啥算法，其实正确的暴力姿势也能出奇迹。
刚开始只想到我们求得每个数的因子个数b[i],对然后巧用break;能混过去；
这种形式：if (ans>b[i]*b[j]) break 一层循环，b数组是按照 因子个数从大到小 排序，所以正确。
但是 我们每次算(a[i],a[j])的因子个数总和时还要 一步一步枚举过去，TLE。
比如这段代码：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<string> using namespace std; #define N 100001 int p[N];
int b[N],t; struct node
{
int x,y;
}a[N];
void prime()
{
for (int i=2;i<N;i++)
if (!b[i])
for (int j=i+i;j<N;j+=i)
b[j]=1; for (int i=2;i<N;i++)
if (!b[i]) p[++t]=i;
} int work(int x,int y)
{
int sum=1;
int t=1;
while (1)
{
if (x==1&&y==1) return sum;
int v=1;
if (x%p[t]==0)
{
while (x%p[t]==0)
{
v++;
x/=p[t];
}
}
if (y%p[t]==0)
{
while (y%p[t]==0)
{
v++;
y/=p[t];
}
}
t++;
sum*=v;
}
} int cmp(node a,node b)
{
return a.y>b.y;
} int main()
{
prime(); memset(b,0,sizeof(b));
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i].x),a[i].y=work(a[i].x,1);
//for (int i=1;i<=n;i++) printf("%d ",a[i].y);
sort(a+1,a+n+1,cmp);
int ans=0;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++){
if (ans>a[i].y*a[j].y) break;
else ans=work(a[i].x,a[j].x);
} printf("%d\n",ans);
return 0;
}
于是看到一个模板:线性帅法，并且每次能求出一个数的前驱素数因子
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<string> using namespace std; #define N 100001 int p[N];
int b[N],t=; struct node
{
int x,y;
}a[N];
void prime()
{
for (int i=;i<N;i++)
{
if (!b[i]) p[++t]=b[i]=i;
for (int j=;j<=t&&p[j]<=b[i]&&p[j]<=N/i;++j) b[i*p[j]]=p[j];
}
b[]=N;
} int work(int x,int y)
{
int sum=;
int c=;
while (x>||y>)
{
if (b[x]<b[y]) c=b[x];
else c=b[y];
int v=;
for (;b[x]==c;x/=c) v++;
for (;b[y]==c;y/=c) v++;
sum*=v;
}
return sum;
}
inline int cmp(node a,node b)
{
return a.y>b.y;
} int main()
{
prime(); int n;
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&a[i].x),a[i].y=work(a[i].x,); sort(a+,a+n+,cmp);
int ans=a[].y;
n=min(n,); for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++){
if (ans>a[i].y*a[j].y) break;
else ans=max(ans,work(a[i].x,a[j].x));
} printf("%d\n",ans);
return ;
}
但是你 会发现还是很慢，超级慢，9000ms 了，然后又看一份代码，发现！！
我们枚举的
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
因为 n可能很大，大概10万，但是后面大多没用，所以我们只要 n<=1000，之类的就够了。 暴力简直可怕