130811個人賽練習BNU-Regionals 2012, Asia - Tokyo

A Ginkgo Numbers

直接暴力查找(m,n)是否為(p,q)的因子

1<m^2+n^2<20000 所以直接來個142x142的循環就行

#include<iostream>   
#include<cstdio>   
#include<algorithm>   
#include<cstring>   
#include<string>   
#include<cmath>   
#include<map>   
using namespace std;  
inline void RD(int &ret)  
{  
    char c;  
    do  
    {  
        c=getchar();  
    }  
    while(c<'0'||c>'9');  
    ret=c-'0';  
    while((c=getchar())>='0'&&c<='9')  
    {  
        ret=ret*10+(c-'0');  
    }  
}  
inline void OT(int a)  
{  
    if(a>=10)  
    {  
        OT(a/10);  
    }  
    putchar(a%10+'0');  
}  
int main()  
{  
    int t,i,j,p,q,x,y,f;  
    RD(t);  
    while(t--)  
    {  
        scanf("%d%d",&p,&q);  
        x=p*p+q*q;  
        if(x<=1)  
        {  
            printf("C\n");  
        }  
        else  
        {  
            f=0;  
            for(i=-142; i<=142; ++i)  
            {  
                for(j=-142; j<=142; ++j)  
                {  
                    y=i*i+j*j;  
                    if(y==0||y==1)  
                    {  
                        continue;  
                    }  
                    if((abs(i)==abs(p)&&abs(j)==abs(q))||(abs(i)==abs(q)&&abs(j)==abs(p)))  
                    {  
                        continue;  
                    }  
                    if((i*p+j*q)%y==0&&(i*q-j*p)%y==0)  
                    {  
                        f=1;  
                        break;  
                    }  
                }  
                if(f==1)  
                {  
                    break;  
                }  
            }  
            if(f==1)  
            {  
                printf("C\n");  
            }  
            else  
            {  
                printf("P\n");  
            }  
        }  
    }  
    return 0;  

B One-Dimensional Cellular Automaton

一道數論題，直接寫TLE無疑，只能YY了一下。各種數組保存。。。寫得都暈了，居然1A。

#include<cstdio>   
#include<algorithm>   
#include<cstring>   
#include<string>   
#include<cmath>   
#define mem(a,b) memset(a,b,sizeof(a))   
#define FOR(a,b,i) for(i=a;i<b;++i)   
#define For(a,b,i) for(i=a;i<=b;++i)   
using namespace std;  
inline void RD(int &ret)  
{  
    char c;  
    do  
    {  
        c=getchar();  
    }  
    while(c<'0'||c>'9');  
    ret=c-'0';  
    while((c=getchar())>='0'&&c<='9')  
    {  
        ret=ret*10+(c-'0');  
    }  
}  
inline void OT(int a)  
{  
    if(a>=10)  
    {  
        OT(a/10);  
    }  
    putchar(a%10+'0');  
}  
int s[51],f[51][51][51],q[51][51],tx[51];  
int main()  
{  
    int n,m,a,b,c,t,i,j,k,l,p,tt;  
    while(1)  
    {  
        RD(n);  
        RD(m);  
        RD(a);  
        RD(b);  
        RD(c);  
        RD(t);  
        if(n==0&&m==0&&a==0&&b==0&&c==0&&t==0)  
        {  
            break;  
        }  
        For(1,n,i)  
        {  
            RD(s[i]);  
        }  
        if(t==0)//等於0時沒有變化，直接輸出   
        {  
            FOR(1,n,i)  
            {  
                OT(s[i]);  
                printf(" ");  
            }  
            OT(s[n]);  
            printf("\n");  
        }  
        else  
        {  
            For(1,n,i)//三維數組保存   
            {  
                f[0][i-1][i]=a;  
                f[0][i][i]=b;  
                f[0][i+1][i]=c;  
            }  
            p=0;  
            while(t>1)//轉化為2進制進行操作   
            {  
                tx[++p]=t%2;  
                t=t/2;  
            }  
            For(1,p/2,i)  
            {  
                tt=tx[i];  
                tx[i]=tx[p-i+1];  
                tx[p-i+1]=tt;  
            }  
            For(1,p,l)  
            {  
                For(1,n,i)  
                {  
                    For(1,n,j)  
                    {  
                        f[l][i][j]=0;  
                    }  
                }  
                For(1,n,k)  
                {  
                    For(1,n,i)  
                    {  
                        For(1,n,j)  
                        {  
                            f[l][i][j]=(f[l][i][j]+f[l-1][i][k]*f[l-1][k][j])%m;  
                        }  
                    }  
                }  
                if(tx[l]==1)  
                {  
                    For(1,n,i)  
                    {  
                        For(1,n,j)  
                        {  
                            q[i][j]=f[l][i][j];  
                            f[l][i][j]=0;  
                        }  
                    }  
                    For(1,n,k)  
                    {  
                        For(1,n,i)  
                        {  
                            For(1,n,j)  
                            {  
                                f[l][i][j]=(f[l][i][j]+q[i][k]*f[0][k][j])%m;  
                            }  
                        }  
                    }  
                }  
            }  
            mem(q,0);  
            For(1,n,k)  
            {  
                For(1,n,i)  
                {  
                    For(1,n,j)  
                    {  
                        q[i][j]=(q[i][j]+s[k]*f[p][k][j])%m;  
                    }  
                }  
            }  
            FOR(1,n,i)  
            {  
                OT(q[1][i]);  
                printf(" ");  
            }  
            OT(q[1][n]);  
            printf("\n");  
        }  
    }  
    return 0;  
}