HDU 4569 (推导)

2019-04-13 14:07发布

站内文章 / 模拟电子
12880 0 1379

Special equations

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 435    Accepted Submission(s): 274
Special Judge

Problem Description 　　Let f(x) = anxn +...+ a1x +a0, in which ai (0 <= i <= n) are all known integers. We call f(x) 0 (mod m) congruence equation. If m is a composite, we can factor m into powers of primes and solve every such single equation after which we merge them using the Chinese Reminder Theorem. In this problem, you are asked to solve a much simpler version of such equations, with m to be prime's square.  
Input 　　The first line is the number of equations T, T<=50.
　　Then comes T lines, each line starts with an integer deg (1<=deg<=4), meaning that f(x)'s degree is deg. Then follows deg integers, representing an to a0 (0 < abs(an) <= 100; abs(ai) <= 10000 when deg >= 3, otherwise abs(ai) <= 100000000, i 　　Remember, your task is to solve f(x) 0 (mod pri*pri)  
Output 　　For each equation f(x) 0 (mod pri*pri), first output the case number, then output anyone of x if there are many x fitting the equation, else output "No solution!"  
Sample Input 4 2 1 1 -5 7 1 5 -2995 9929 2 1 -96255532 8930 9811 4 14 5458 7754 4946 -2210 9601  
Sample Output Case #1: No solution! Case #2: 599 Case #3: 96255626 Case #4: No solution!  

题意：求一个方程模m^2为0是否有解。 因为m是素数，所以方程模m^2为0必然需要方程模m为0，而所有的x(x>=m)模m为0，必 然有(x-m)模m为0. 所以就可以寻找[0,m-1]中f(x)模m为0的x，然后判断x+m,x+2m....是不是满足。 #include #include #include #include #include #include #include #include using namespace std; #define maxn 11 int n; long long a[maxn]; long long m, mm; long long f1 (long long x) { long long ans = 0; for (int i = n; i >= 0; i--) { long long cur = 1; for (int j = 0; j < i; j++) cur *= x, cur %= m; ans += cur*a[i]; ans = (ans%m+m)%m; } return ans; } long long f2 (long long x) { long long ans = 0; for (int i = n; i >= 0; i--) { long long cur = 1; for (int j = 0; j < i; j++) cur *= x, cur %= mm; ans += cur*a[i]; ans = (ans%mm+mm)%mm; } return ans; } int main () { //freopen ("in.txt", "r", stdin); int t, kase = 0; scanf ("%d", &t); while (t--) { scanf ("%d", &n); for (int i = n; i >= 0; i--) { scanf ("%lld", &a[i]); } scanf ("%lld", &m); mm = m*m; printf ("Case #%d: ", ++kase); long long x, ans; for (x = 0; x < m; x++) { if (f1 (x) == 0) { for (ans = x; ans < m*m; ans += m) { if (f2 (ans) == 0) { printf ("%lld ", ans); goto out; } } } } printf ("No solution! "); out: ; } return 0; }