HDU 4394 - Digital Square（BFS+乘法原理）

#include <stdio.h>  
#include <math.h>  
#define LL long long  
typedef struct 
{ 
    LL num; 
    int len; 
} digit; 
 
LL ans,n; 
LL p[18]; 
int len; 
bool f; 
digit q[100005]; 
int bfs(int cur) 
{ 
    if(f)return 0; 
    int front=0,rear=0; 
    for(int i=0; i<=9; i++) 
    { 
        LL t=i*p[0]; 
        if((t*t)%p[1]==n%p[1]) 
        { 
            q[rear].num=t; 
            q[rear].len=1; 
            rear++; 
        } 
    } 
    //printf("%d\n",rear);  
    while(front<rear) 
    { 
        LL u=q[front].num; 
        int l=q[front].len; 
        //printf("%I64d\n",u);  
 
        if((u*u)%p[len]==n) 
        { 
            f=true; 
            if(u<ans) 
            ans=u; 
        } 
        if(l>len)return 0; 
        //if(u==0)l=1;  
        //printf("%I64d\n",l);  
        for(int i=0; i<=9; i++) 
        { 
            LL t=i*p[l]+u; 
            if((t*t)%p[l+1]==n%p[l+1]) 
            { 
                q[rear].num=t; 
                q[rear].len=l+1; 
                rear++; 
            } 
        } 
        front++; 
    } 
    return 0; 
} 
 
int main() 
{ 
    p[0]=1; 
    for(int i=1; i<18; i++) 
    { 
        p[i]=p[i-1]*10; 
    } 
    int T; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%I64d",&n); 
        len=log10(n)+1; 
        int k=n%10; 
        f=false; 
        ans=1LL<<62; 
        if(k==0||k==1||k==4||k==5||k==6||k==9) 
        { 
            bfs(0); 
        } 
        if(!f) 
            printf("None\n"); 
        else 
            printf("%I64d\n",ans); 
    } 
    return 0; 
} 

#include <stdio.h>
#include <math.h>
#define LL long long
typedef struct
{
    LL num;
    int len;
} digit;

LL ans,n;
LL p[18];
int len;
bool f;
digit q[100005];
int bfs(int cur)
{
    if(f)return 0;
    int front=0,rear=0;
    for(int i=0; i<=9; i++)
    {
        LL t=i*p[0];
        if((t*t)%p[1]==n%p[1])
        {
            q[rear].num=t;
            q[rear].len=1;
            rear++;
        }
    }
    //printf("%d\n",rear);
    while(front<rear)
    {
        LL u=q[front].num;
        int l=q[front].len;
        //printf("%I64d\n",u);

        if((u*u)%p[len]==n)
        {
            f=true;
            if(u<ans)
            ans=u;
        }
        if(l>len)return 0;
        //if(u==0)l=1;
        //printf("%I64d\n",l);
        for(int i=0; i<=9; i++)
        {
            LL t=i*p[l]+u;
            if((t*t)%p[l+1]==n%p[l+1])
            {
                q[rear].num=t;
                q[rear].len=l+1;
                rear++;
            }
        }
        front++;
    }
    return 0;
}

int main()
{
    p[0]=1;
    for(int i=1; i<18; i++)
    {
        p[i]=p[i-1]*10;
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&n);
        len=log10(n)+1;
        int k=n%10;
        f=false;
        ans=1LL<<62;
        if(k==0||k==1||k==4||k==5||k==6||k==9)
        {
            bfs(0);
        }
        if(!f)
            printf("None\n");
        else
            printf("%I64d\n",ans);
    }
    return 0;
}