题解 | #完全平方数的尾巴#
完全平方数的尾巴
http://www.nowcoder.com/practice/ddbfc06b8c06403687f8e8ff4d57d5ad
题意：
给你一个数
，判断这个数是不是某个平方数对
取模的结果
解法一（扩展欧几里得）
我们记这个平方数为
由
可得
显然这是一个不定方程，于是我们可以用扩展欧几里得算法求解
具体的，我们可以解出)
的解
于是原方程的一个解为：%7D%2Cb_0%3Db'*%5Cfrac%7Bx%7D%7Bgcd(1%2C-1000)%7D)
我们设%7C)
，则的通式为
于是我们只需要最多枚举到
判断即可
代码：
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;
}
}; 时间复杂度：
