首页 > 代码库 > 1046:Square Number
1046:Square Number
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
给定正整数b，求最大的整数a，满足a*(a+b) 为完全平方数
- 输入
- 多组数据，第一行T，表示数据数。对于每组数据，一行一个正整数表示b。
T <= 10^3， 1 <= b <= 10^9 - 输出
- 对于每组数据，输出最大的整数a，满足a*(a+b)为完全平方数
- 样例输入
3136
- 样例输出
01
2
思路：a*(a+b)；gcd(a,b) = gcd（a,a+b），这个符合辗转相除，然后a*（a+b）=gcd^2(a1)*(a1+b1),那么a1与a1+b1互质
然后a1必定为一个数的平方x1^2，（a1+b1）为某个数的平方y^2;那么gcd（x,y）=1,然后b1=（x+y）(x-y);那么a=gcd*x^2,b1为
b的因子，所以枚举b1,再枚举b1的因子解出x，y1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<set> 7 #include<math.h> 8 using namespace std; 9 typedef long long LL;10 LL gcd(LL n,LL m) {11 if(m == 0)return n;12 else return gcd(m,n%m);13 }14 LL slove(LL n);15 int main(void) {16 int T;17 scanf("%d",&T);18 while(T--) {19 LL n;20 scanf("%lld",&n);21 printf("%lld\n",slove(n));22 }23 return 0;24 }25 LL slove(LL n) {26 LL maxx = -1;27 LL x = sqrt(1.0*n);28 int i,j;29 for(i = 1; i <= x ; i++) {30 if(n%i==0) {31 int x1 = i;32 int x2 = n/i;33 for(j = 1; j <= sqrt(1.0*x1); j++) {34 if(x1%j == 0) {35 LL k = x1/j;36 //if(gcd(k,j)==1)37 {38 if((k+j)%2==0) {39 LL xx = (k-j)/2;40 LL yy = (k+j)/2;41 if(gcd(xx,yy)==1)42 maxx = max(maxx,xx*xx*x2);43 }44 }45 }46 }47 for(j = 1; j <= sqrt(1.0*x2); j++) {48 if(x2%j == 0) {49 LL k = x2/j;50 //if(gcd(k,j)==1)51 {52 if((k+j)%2==0) {53 LL xx = (k-j)/2;54 LL yy = (k+j)/2;55 if(gcd(xx,yy)==1)56 maxx = max(maxx,xx*xx*x1);57 }58 }59 }60 }61 }62 }63 return maxx;64 }
1046:Square Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。