HDU 4569 Special equations 2012長沙招待試合E題(数学知識)
Special equations
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 178 Accepted Submission(s): 87 Special Judge
Problem Description
Let f(x) = a
nx
n +...+ a
1x +a
0, 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 (0 < abs(a
n) <= 100; abs(a
i) <= 10000 when deg >= 3, otherwise abs(a
i) <= 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
Sample Output
テーマ:
関数をあげる f(x) = a
n
x
n
+...+ a
1
x +a
0 最大Nは4ビットで、いずれかのxを入力してf(x)%(prime*prime)=0にします.見つからなかったらNO solutionを出力!
問題を解く構想:中国の残りの定理が少し愚かになったのを見始めた.以前は中国の残りの定理のいくつかの定理を塗っただけで、一般的には多くの同余方程式を求めていたからだ.それからチームがあって、それから真剣に見ました.そして暴力をやることにし、primeの範囲1~10^4を見て、列挙すると10^8ですが暴力がタイムアウトし、テストコードを実行するのに数秒かかりました.后で分からないで大白の中で中国の残りの定理を话すことを见始めます..あと30分ほどで急に霊光が現れ、primeを0にしてから判断を続けることができると思います.そしてすぐにコードを変更します.その後WAになって、事実は当時ただ1つの変数が間違っていたことを証明しました.のp+=mo直接毎回moをプラスして、どうして+tに書きました!!当時はよく考えていなかったが、p++肯定TLEに変えた.降りてからよく考えてみると、抜け穴がないことに気づいた.
思考過程:f(x)%(mo*mo)=0の必要条件がf(x)%(mo)=0であれば、f(x+k*mo)%mo=0はf(x)%mo=0と等価であり、自分で紙に描いてもよい.その时、主に后ろに定数の项目があって、それからそれを右に置いてTATに行く必要があるかどうかを考えていました!実は必要ありません.それから直接0~moの1つの区間の中で先にf(x)%mo==0のを探して、もし木が直接出力No sulotionがあるならば!もしあるならば、+moはできるかどうかを判断します
合数をいくつかの素数に分解して乗算したもので、主に中国の残りの定理に驚かされ、身につけなければならない知識は理解するだけではない.がんばって!
タイトルアドレス:Special equations
ACコード:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 178 Accepted Submission(s): 87 Special Judge
Problem Description
Let f(x) = a
nx
n +...+ a
1x +a
0, 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 (0 < abs(a
n) <= 100; abs(a
i) <= 10000 when deg >= 3, otherwise abs(a
i) <= 100000000, i
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!
テーマ:
関数をあげる f(x) = a
n
x
n
+...+ a
1
x +a
0 最大Nは4ビットで、いずれかのxを入力してf(x)%(prime*prime)=0にします.見つからなかったらNO solutionを出力!
問題を解く構想:中国の残りの定理が少し愚かになったのを見始めた.以前は中国の残りの定理のいくつかの定理を塗っただけで、一般的には多くの同余方程式を求めていたからだ.それからチームがあって、それから真剣に見ました.そして暴力をやることにし、primeの範囲1~10^4を見て、列挙すると10^8ですが暴力がタイムアウトし、テストコードを実行するのに数秒かかりました.后で分からないで大白の中で中国の残りの定理を话すことを见始めます..あと30分ほどで急に霊光が現れ、primeを0にしてから判断を続けることができると思います.そしてすぐにコードを変更します.その後WAになって、事実は当時ただ1つの変数が間違っていたことを証明しました.のp+=mo直接毎回moをプラスして、どうして+tに書きました!!当時はよく考えていなかったが、p++肯定TLEに変えた.降りてからよく考えてみると、抜け穴がないことに気づいた.
思考過程:f(x)%(mo*mo)=0の必要条件がf(x)%(mo)=0であれば、f(x+k*mo)%mo=0はf(x)%mo=0と等価であり、自分で紙に描いてもよい.その时、主に后ろに定数の项目があって、それからそれを右に置いてTATに行く必要があるかどうかを考えていました!実は必要ありません.それから直接0~moの1つの区間の中で先にf(x)%mo==0のを探して、もし木が直接出力No sulotionがあるならば!もしあるならば、+moはできるかどうかを判断します
合数をいくつかの素数に分解して乗算したもので、主に中国の残りの定理に驚かされ、身につけなければならない知識は理解するだけではない.がんばって!
タイトルアドレス:Special equations
ACコード:
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
int a[5],n,mo,Mo;
__int64 cal1(int t) // mo
{
int i,j;
__int64 res=a[0];
for(i=1;i<=n;i++)
{
__int64 tmp=a[i];
for(j=1;j<=i;j++)
{
tmp=tmp*t;
tmp=tmp%mo;
}
res=(res+tmp)%mo;
}
return res;
}
__int64 cal2(int t) // mo*mo
{
int i,j;
__int64 res=a[0];
for(i=1;i<=n;i++)
{
__int64 tmp=a[i];
for(j=1;j<=i;j++)
{
tmp=tmp*t;
tmp=tmp%Mo;
}
res=(res+tmp)%Mo;
}
return res;
}
int main()
{
int tes,cas,t,i,p;
scanf("%d",&tes);
for(cas=1;cas<=tes;cas++)
{
scanf("%d",&n);
int flag=0;
for(i=n;i>=0;i--)
scanf("%d",&a[i]);
scanf("%d",&mo);
Mo=mo*mo;
/*for(i=n;i>=0;i--)
cout<<a[i]<<" ";
cout<<mo<<endl;*/
for(t=0;t<=mo;t++)
{
if(cal1(t)==0) // mo
{
for(p=t;p<=Mo;p+=mo) // TAT
{
if(cal2(p)==0)
{
flag=1;
break;
}
}
}
if(flag==1)
break;
}
if(flag==1)
printf("Case #%d: %d
",cas,p);
else
printf("Case #%d: No solution!
",cas);
}
return 0;
}