HDU 4569 Special equations(取模)

Special equations

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

　　Let f(x) = a _nx ⁿ +...+ a ₁x +a ₀, in which a _i (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 a _n to a ₀ (0 < abs(a _n) <= 100; abs(a _i) <= 10000 when deg >= 3, otherwise abs(a _i) <= 100000000, i<n). The last integer is prime pri (pri<=10000).
　　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

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!

-------------------------------------------------------

题意：给你函数 f(x)

_{最多N就4位，输入任意一个x使f(x)%(prime*prime)=0。}

首先要找一个 f(x) % prime = 0 ，只有满足这个条件 f(x) % (prime * prime) 才有可能等于0，对于f(x) % prime，可以枚举 0 - prime，如果满足条件那么在判断（ x + prime * k ) % （prime * prime)是否满足条件

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 typedef long long LL;
 7 LL a[5], P;
 8 int deg;
 9 bool func(LL x, LL mod)
10 {
11     LL res = 0, now = 1;
12     for (int i = 0; i <= deg; i++)
13     {
14         res = (res + now * a[i]) % mod;
15         now = (now * x) % mod;
16     }
17     if (res % mod)
18         return 1;
19     return 0;
20 }
21 int main()
22 {
23     int test;
24     scanf("%d", &test);
25     for (int t = 1; t <= test; t++)
26     {
27         scanf("%d", &deg);
28         for (int i = deg; i >= 0; i--)
29         {
30             scanf("%I64d", &a[i]);
31         }
32         scanf("%I64d", &P);
33         LL ans = -1;
34         int flag = false;
35         for (LL i = 0; i <= P; i++)
36         {
37             if (func(i, P))
38                 continue;
39             for (LL j = i; j <= P * P; j += P)
40             {
41                 if (func(j, P * P))
42                     continue;
43                 flag = true;
44                 ans = j;
45                 break;
46             }
47             if (flag)
48                 break;
49         }
50         printf("Case #%d: ", t);
51         if (flag)
52             printf("%I64d
", ans);
53         else
54             printf("No solution!
");
55     }
56     return 0;
57 }

View Code