学步园

今天周赛，怒爆1题。。 可以看到，仍需努力。不多说，继续走。

比赛地址：点击打开链接

比赛大部分时间都在搞A题，20A

一开始，根本没有看好题。我擦。一大堆WA。

由于，最近搞了Hash，就想到了这种方法。不过，一开始，处理的和一坨屎差不多。最后重新写了一遍，看起来比较合乎逻辑的。

直接代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int N=122055;
int p1[N],p2[N];
int main(){
    memset(p1,0,sizeof(p1));
    memset(p2,0,sizeof(p2));
    for(int i=1;i<=245;i++)
    p1[i*i]=1;
    for(int i=1;i<=245;i++){
        for(int j=i;j<=245;j++)
        p2[i*i+j*j]=1;
    }
    int T;
    while(~scanf("%d",&T)){
        while(T--){
            int n;
            scanf("%d",&n);
            if(n==0) {
                printf("1\n");
                continue;
            }
            if(p1[n]) {
                printf("1\n");
                continue;
            }
            else if(p2[n]){
                printf("2\n");
                continue;
            }
            else {
                bool flag=false;
                for(int i=1;i<=n/2;i++){
                    if((p1[i]&&p2[n-i])||(p2[i]&&p1[n-i]))
                    {printf("3\n");flag=true;break;}
                }
                if(flag) continue;
            }
            printf("4\n");
        }
    }
    return 0;
}

思路就是，把一个数的平方和两个数的平方，都给标记。这样，就可以判断是否可以一个或者两个。

三个就的一个和两个的结合了。其他情况就是四个了。

在判断三个的时候，如果写成if（p1[i]&&p2[n-i]）会超时。可以像上述代码一样，只判断一半。

C题，比赛的时候没有做出来。

后来，听了一种说法，就是，对于这种，高次幂，小素数，一定会存在循环。。

然后，有了这种想法，就很容易了。

代码：

#include <cstdio>
#include <cstring>

const long long Base=9901;
const int N=9905;
int out[N];
bool mark[N];

int main(){
    freopen("2.txt","w",stdout);
    long long n,k;
    while(~scanf("%lld %lld",&n,&k)){
        memset(mark,0,sizeof(mark));
        long long i,tmp1=1,ans=0,x=0;
        for(i=1;i<=k;i++){
            tmp1=(tmp1*n)%Base;
            ans=(ans+tmp1)%Base;
            if(mark[ans]) break;
            out[x++]=ans;mark[ans]=true;
        }
        if(i>k) printf("%d\n",out[x-1]);
        else printf("%d\n",out[k%x-1]);
    }
    return 0;
}

对于这次比赛，不管结果是这么，（结果已经摆在那了）。

我只想说，继续。。