题意:
有三个二次函数,分别是$x^2 + a_1x + b_1$, $x^2 + a_2x + b_2$, $x^2 + a_3x + b_3$
现在要找三个整数$x_1, x_2, x_3$, 使得三个函数值中至少有两个相等。
思路:
主要的难点是要找三个整数。
Camp时候洪老师说的平移啥啥的,理解不了......
看了网上另一个题解的思路。
假设两个二次函数相等的函数值是$y$, 并假设是第一个和第二个相等
那么我们可以知道$x_1 =- \frac{a_1 + \sqrt{a_1^2 - 4(b_1 - y)}}{2}, x_2 =- \frac{a_2 + \sqrt{a_2^2 - 4(b_2 - y)}}{2}$
令$T^2 = a_1^2 - 4(b_1 - y), t^2 = a_2^2 - 4(b_2 - y)$
可以得到$T^2 - t^2 = a_1^2 - 4b_1 - a_2^2 + 4b_2 = (T+t)(T-t)$
于是我们进行因式分解,枚举$T^2-t^2$的因子,判断得到的$x_1, x_2$是否为整数。
对于$T^2-t^2$为0和1时进行特判就行了。
对于每一对$a$和$b$,判断是否有这样两个整数解。
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include<set>
8 #include
9 #include
10
11 using namespace std;
12 typedef long long LL;
13
14 LL a[3], b[3];
15 int t;
16 LL ans1, ans2;
17
18 bool solve(LL a1, LL b1, LL a2, LL b2)
19 {
20 int sub &#61; abs(a1 * a1 - 4 * b1 - a2 * a2 &#43; 4 * b2);
21 if(sub &#61;&#61; 0){
22 if((a1 - a2) % 2 &#61;&#61; 0){
23 ans1 &#61; 0;
24 ans2 &#61; (a1 - a2) / 2;
25 return true;
26 }
27 else return false;
28 }
29 else if(sub &#61;&#61; 1){
30 if(a1 % 2 !&#61; a2 % 2){
31 if(a1 * a1 - 4 * b1 > a2 * a2 - 4 * b2 && a1 % 2){
32 ans1 &#61; (1 - a1) / 2;
33 ans2 &#61; -a2 / 2;
34 return true;
35 }
36 else if(a1 * a1 - 4 * b1
37 ans2 &#61; (1 - a2) / 2;
38 ans1 &#61; -a1 / 2;
39 return true;
40 }
41 else return false;
42 }
43 return false;
44 }
45 else{
46 for(int i &#61; 1; i * i ){
47 if(!(sub % i) && !((sub / i &#43; i) % 2) && !((i - sub / i) % 2)){
48 LL T &#61; (sub / i &#43; i) / 2;
49 LL t &#61; (i - sub / i) / 2;
50 if(a1 * a1 - 4 * b1
51 if(!((T &#43; a1) % 2) && !((t &#43; a2) % 2)){
52 ans1 &#61; -(a1 &#43; T) / 2;
53 ans2 &#61; -(a2 &#43; t) / 2;
54 return true;
55 }
56 }
57 }
58 return false;
59 }
60 }
61
62 void work()
63 {
64 for(int i &#61; 0; i <3; i&#43;&#43;){
65 for(int j &#61; i &#43; 1; j <3; j&#43;&#43;){
66 if(solve(a[i], b[i], a[j], b[j])){
67 if(i &#61;&#61; 0)
68 {
69 printf("%lld %lld %lld\n", ans1, j &#61;&#61; 1?ans2:0, j&#61;&#61;1?0:ans2);
70 //return;
71 }
72 else{
73 printf("0 %lld %lld\n", ans1, ans2);
74 //return ;
75 }
76 return;
77 }
78 }
79 }
80 }
81
82 int main()
83 {
84 scanf("%d", &t);
85 while(t--){
86 for(int i &#61; 0; i <3; i&#43;&#43;){
87 scanf("%lld%lld", &a[i], &b[i]);
88 }
89 work();
90 }
91
92
93 return 0;
94 }