1046:Square Number
2024-09-07 21:10:27
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
给定正整数b，求最大的整数a，满足a*(a+b) 为完全平方数
- 输入
- 多组数据，第一行T，表示数据数。对于每组数据，一行一个正整数表示b。
T <= 10^3， 1 <= b <= 10^9 - 输出
- 对于每组数据，输出最大的整数a，满足a*(a+b)为完全平方数
- 样例输入
-
3
1
3
6 - 样例输出
-
0
1
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 }
最新文章
- 移动端HTML5<video>视频播放优化实践
- javascript除法如何取整
- bzoj4409&&bzoj4410&&bzoj4411[Usaco2016 Feb Platinum]题解
- HttpHandler和ashx要实现IRequiresSessionState接口才能访问Session信息（转载）
- 《WPF程序设计指南》读书笔记——第9章 路由输入事件
- 改ucosii的中断禁止和恢复代码,这是一个荒谬的错误【 mrs msr】
- sqlserver 游标写法
- Python学习的相关文件链接
- python语法_函数
- python之把字符串形式的函数编译执行
- BZOJ3655 : 神经错乱数
- python第三十七天--异常--socket
- 【3-20】html 基本知识/表格/超链接
- non-deterministic-turing-machine
- ew代理实战
- javascript中原型,构造器,还有E5扩展的默认成员
- [CF126D]Fibonacci Sums/[BJOI2012]最多的方案
- LaTeX排版设置图表的位置 Positioning images and tables
- 51Nod 1010 只包含因子2 3 5的数 | 预处理+二分
- [Leetcode Week15]Populating Next Right Pointers in Each Node II