题解 | #完全平方数的尾巴#

完全平方数的尾巴

http://www.nowcoder.com/practice/ddbfc06b8c06403687f8e8ff4d57d5ad

题意：

给你一个数 $x$ ，判断这个数是不是某个平方数对 $1000$ 取模的结果

解法一（扩展欧几里得）

我们记这个平方数为 $a$

由

$a\%1000=x$

可得

$a-k*1000=x$

显然这是一个不定方程，于是我们可以用扩展欧几里得算法求解

具体的，我们可以解出 $1*a'-1000*k'=gcd(1,-1000)$ 的解

于是原方程的一个解为： $a_0=a'*\frac{x}{gcd(1,-1000)},b_0=b'*\frac{x}{gcd(1,-1000)}$

我们设 $d=|gcd(1,-1000)|$ ，则 $a$ 的通式为 $a=a_0+\frac{1000}{d}$

于是我们只需要最多枚举 $a$ 到 $1000^2$ 判断即可

代码：

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    int exgcd(int a,int b,int& x,int& y){//扩展欧几里得算法
        if(b==0){
            x=1,y=0;//特解
            return a;
        }
        int d=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return d;
    }
    inline bool check(int x){//判断是否是完全平方数
        int t=sqrt(x);
        return t*t==x;
    }
    bool solve(int x) {
        //a-k*1000=x
        int a,k;
        int d=exgcd(1,-1000,a,k);
        a*=x/d;
        //a+=-1000/d
        //k-=1/d
        int p=abs(-1000/d);
        while(a<0){
            a+=p;//先加到正数
        }
        while(a<1000000){//枚举到1000^2
            a+=p;
            if(check(a))return true;
        }
        return false;
    }
};

时间复杂度： $O(P^2)$ ， $P$ 为模数，本题中为 $1000$ ，由于数字 $a$ 最多要枚举到 $P^2$ ，故时间复杂度为 $O(P^2)$

空间复杂度： $O(logP)$ ，由于扩展欧几里得递归深度为 $O(logP)$ 级别，故总的空间复杂度为 $O(logP)$

解法二（枚举）

我们可以直接枚举 $0\sim 1000$ ，并判断其平方是否满足条件即可

代码：

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    bool solve(int x) {
        for(int i=0;i<=1000;i++){
            if(i*i%1000==x)return true;//判断
        }
        return false;
    }
};