最后一个点TLE。。。╮(╯▽╰)╭

SZnP @ 2021-08-24 21:48:11

#include <iostream>
#include <cstdio> 
using namespace std;
int v[50000];
bool ss(int a)
{
    if(v[a]!=-1)return v[a];
    if(a<=1){v[a]=0;return 0;}
    for(int i=2;i<a;i++)
    if(a%i==0){v[a]=0;return 0;}
    v[a]=1;
    return 1;
}
int main()
{
    memset(v,-1,sizeof(v));
    int n,imin=65536,jmin=65536,k;
    cin>>n;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    {
        if(n-i-j>=0&&ss(i)&&ss(j)&&ss(n-i-j))
        if(i<imin)
        {
            imin=i;
            jmin=j;
            k=n-i-j;
        }
        else
        if(i==imin&&j<jmin)
        {
            imin=i;
            jmin=j;
            k=n-i-j;
        }
    }
    printf("%d %d %d",imin,jmin,k);
    return 0;
}

by SZnP @ 2021-08-24 21:50:22

19813

3 17 19793

--------------------------------

Process exited after 4.678 seconds with return value 0

请按任意键继续. . .

by SZnP @ 2021-08-24 21:50:51

以上是最后一个点的数据

by 一SakuRa @ 2021-08-24 21:51:08

@LXLLZG

bool ss(int a)
{
    if(v[a]!=-1)return v[a];
    if(a<=1){v[a]=0;return 0;}
    for(int i=2;i<a;i++)
    if(a%i==0){v[a]=0;return 0;}
    v[a]=1;
    return 1;
}

判断素数部分可以优化一下，别的不清楚

by SZnP @ 2021-08-24 21:52:43

记录

by SZnP @ 2021-08-24 21:54:02

@一SakuRa 谢谢

by SZnP @ 2021-08-25 10:11:49

然而好像并没有什么用。。。

by QuAckB33 @ 2021-08-25 12:25:09

@LXLLZG 开O2就过了

by SZnP @ 2021-08-25 16:09:26

@Chuuyasang 还真是。。。

by 雨伞CKY @ 2021-11-13 18:09:14

@LXLLZG 尽管开启 O2 优化可以轻松 AC， 但是还是应该优化一下判断质数（素数）的函数。

建议你参考 Rosmarinus 的博客《Rosmarinus の 奇妙数论学习笔记》中的【质数】部分，修改你判断质数的函数。