题意:

给你一个数,判断这个数是不是某个平方数对取模的结果

解法一(扩展欧几里得)

我们记这个平方数为

可得

显然这是一个不定方程,于是我们可以用扩展欧几里得算法求解
具体的,我们可以解出的解
于是原方程的一个解为:
我们设,则的通式为
于是我们只需要最多枚举判断即可
代码:
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;
    }
};
时间复杂度:为模数,本题中为,由于数字最多要枚举到,故时间复杂度为
空间复杂度:,由于扩展欧几里得递归深度为级别,故总的空间复杂度为

解法二(枚举)

我们可以直接枚举,并判断其平方是否满足条件即可
代码:
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;
    }
};
时间复杂度:,由于我们枚举,故时间复杂度为
空间复杂度:,程序只用了有限个变量,且没有递归操作,故空间复杂度为