2015
07-25

# Special equations

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.

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<n). The last integer is prime pri (pri<=10000).

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<n). The last integer is prime pri (pri<=10000).

4
2 1 1 -5 7
1 5 -2995 9929
2 1 -96255532 8930 9811
4 14 5458 7754 4946 -2210 9601

Case #1: No solution!
Case #2: 599
Case #3: 96255626
Case #4: No solution!

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[10];
long long getf(long long x,int n)
{
long long sum=0;
for(int i=0; i<n; i++)
sum+=a[i],sum*=x;
return sum+a[n];
}
void solve(int n,long long pri)
{
long long i,j,mod=pri*pri;
for(i=0; i<pri; i++)
if(getf(i,n)%pri==0)
for(j=i; j<mod; j+=pri)
if(getf(j,n)%mod==0)
{
printf("%I64d\n",j);
return;
}
puts("No solution!");
}
int main()
{
int t,n,ca=0;
long long pri;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n+1; i++)
scanf("%I64d",&a[i]);
scanf("%I64d",&pri);
printf("Case #%d: ",++ca);
solve(n,pri);
}
return 0;
}