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