http://acm.hdu.edu.cn/showproblem.php?pid=2394题目的大概意思就是，判断关于x的二次同余方程 a x^2 + b x + c = 0 ( mod 2 ^32 ) 是否有解
看到这道题目的时候刚好看了一些二次互反律之类的知识，思维被定向到了那边，又在网上找了一些资料，但是都不能解决此题（起码我没有想出来怎么办，大牛勿鄙视）。跟haozi讨论了一下，也没什么结果，后来haozi用java的大数把这题过了，我也不知道他怎么做的，他只说是很暴力的方法。今天在ACM_DIY群里请教了一下 UESTC 的 love8909 大牛，原来只要分来讨论 a b c 的奇偶性一共8种情况，比如：abc都是偶数，那么方程等价于 a/2 x^2 + b/2 x + c/2 = 0 ( mod 2 ^31 )， 通过讨论可以将mod的数降下来，一直到2^0为止，若能达到，必然有解，还有一些情况详见我代码:
hdu_2394
1
#include <cstdio>
2#include <iostream>
3#include <map>
4#include <queue>
5#include <complex>
6#include <algorithm>
7#include <cmath>
8#include <cstring>
9using namespace std;
10typedef __int64 ll;
11
12bool solve( ll a, ll b, ll c, int k )
13
{
14
if( k == 0 )
15
{
16 return true;
17
}
18 if( a % 2 == 0 )
19 {
20 if( b % 2 == 0 )
21 {
22 if( c % 2 == 0 ) // 0 0 0
23 {
24 return solve( a / 2, b / 2, c / 2, k - 1 );
25 }
26 else // 0 0 1
27 {
28 return false;
29 }
30 }
31 else
32 {
33 if( c % 2 == 0 ) // 0 1 0
34 {
35 return solve( 2 * a, b, c / 2, k - 1 );
36 }
37 else // 0 1 1
38 {
39 return solve( 4 * a, 4 * a + 2 * b, a + b + c, k -1 );
40 }
41 }
42 }
43 else
44 {
45 if( b % 2 == 0 )
46 {
47 if( c % 2 == 0 ) // 1 0 0
48 {
49 return solve( 2 * a, b, c / 2, k - 1 );
50 }
51 else // 1 0 1
52 {
53 return solve( 4 * a, 4 * a + 2 * b, a + b + c, k - 1 );
54 }
55 }
56 else
57 {
58 if( c % 2 == 0 ) // 1 1 0
59 {
60 return solve( 2 * a, b, c / 2, k - 1 ) ||
61 solve( 4 * a, 4 * a + 2 * b, a + b + c, k - 1 );
62 }
63 else // 1 1 1
64 {
65 return false;
66 }
67 }
68 }
69
}
70
71int main(int argc, char *argv[])
72{
73 int n;
74 ll a, b, c;
75 scanf("%d",&n);
76 while( n-- )
77 {
78 scanf("%I64d%I64d%I64d",&a,&b,&c);
79 if( solve( a, b, c, 32 ) )printf("YES\n");
80 else printf("NO\n");
81 }
82 return 0;
83}
84