#ACM2021_25. 有关2022

今天整了个小题，但可惜超时了（悲

我之前的做法（暴力枚举，但超时）

#include <stdio.h>
#include <string.h>


int main(int argc, const char *argv[])
{
    int a,b,c,d,e,sum,k;
    int count=0;
    scanf("%d",&e);
    for(a=0; a<=2022; a++)
    {
        for(b=0; b<=2022; b++)
        {
            for(c=0; c<=2022; c++)
            {

                d=2022-a-b-c;
                sum=(a*a+b*b+c*c+d*d)%2022;
                k=e%2022;
                if(d>0&&sum==k)
                {
                    count++;
                }
            }
        }
    }
    printf("%d\n",count%2022);
    return 0;
}
于是我找我的好兄弟求助
算法改进如下：

#include <stdio.h>
#include <string.h>


int main(int argc, const char *argv[])
{
    int a,b,c,d,e,sum,k;
    int answer[]= {1,1,6,12,24};
    int count=0;
    scanf("%d",&e);
    k=e%2022;
    for(a=0; a<=2022/4; a++)
    {
        for(b=a; b<=(2022-a)/3; b++)
        {
            for(c=b; c<=(2022-a-b)/2; c++)
            {

                d=2022-a-b-c;
                sum=(a*a+b*b+c*c+d*d)%2022;

                if(sum==k)
                {
                    count+=answer[1+(a!=b)+(b!=c)+(c!=d)];//判断有几个重复的直接加解的个数
                }
            }
        }
    }
    printf("%d\n",count%2022);
    return 0;
}

本质上还是重复枚举改为了去除掉重复再相加的算法，节约时间啊~