题意&＃xff1a;
有三个二次函数&＃xff0c;分别是$x^2 &＃43; a_1x &＃43; b_1$, $x^2 &＃43; a_2x &＃43; b_2$, $x^2 &＃43; a_3x &＃43; b_3$
现在要找三个整数$x_1, x_2, x_3$&＃xff0c; 使得三个函数值中至少有两个相等。
思路&＃xff1a;
主要的难点是要找三个整数。
Camp时候洪老师说的平移啥啥的&＃xff0c;理解不了......
看了网上另一个题解的思路。
假设两个二次函数相等的函数值是$y$&＃xff0c; 并假设是第一个和第二个相等
那么我们可以知道$x_1 &＃61;- \frac{a_1 &＃43; \sqrt{a_1^2 - 4(b_1 - y)}}{2}, x_2 &＃61;- \frac{a_2 &＃43; \sqrt{a_2^2 - 4(b_2 - y)}}{2}$
令$T^2 &＃61; a_1^2 - 4(b_1 - y), t^2 &＃61; a_2^2 - 4(b_2 - y)$
可以得到$T^2 - t^2 &＃61; a_1^2 - 4b_1 - a_2^2 &＃43; 4b_2 &＃61; (T&＃43;t)(T-t)$
于是我们进行因式分解&＃xff0c;枚举$T^2-t^2$的因子&＃xff0c;判断得到的$x_1, x_2$是否为整数。
对于$T^2-t^2$为0和1时进行特判就行了。
对于每一对$a$和$b$&＃xff0c;判断是否有这样两个整数解。
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 }
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号