hihocoder 1165 : 益智游戏

时间限制: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，之类的就够了。

暴力简直可怕

巴特西

hihocoder 1165 : 益智游戏

描述

输入

输出

最新文章

热门文章