2015
04-13

# Common Roots

We have many polynomials modulo p (p is a prime number). An interesting issue would be to determine whether they have some roots in common. Notice roots we mention here are integers in modulo p system (0 <= root < p). Moreover, if the given polynomial is of order r, we will guarantee that it has r roots.
For example, we have
x^2 + 13x + 36 (mod 37)
x^3 + 14x^2 + 49x + 36 (mod 37)
If x = 33 or x = 28, both of them would give the value of 0. So 33 and 28 are the roots in common.

There are many test cases (less than1000).
In each case, the integer in the first line is n (the number of polynomials in this case). Then n lines followed. Each of them starts with an integer r (order of polynomials, r <= 50), and r + 1 integers (a(r), a(r-1) ,…, a(0)), which means the polynomial goes like:
a(r) * x^r + a(r-1) * x^(r-1) + … +a(1) * x + a(0) (mod 999983).
To make it easier, p is set to be 999983, as you see.

There are many test cases (less than1000).
In each case, the integer in the first line is n (the number of polynomials in this case). Then n lines followed. Each of them starts with an integer r (order of polynomials, r <= 50), and r + 1 integers (a(r), a(r-1) ,…, a(0)), which means the polynomial goes like:
a(r) * x^r + a(r-1) * x^(r-1) + … +a(1) * x + a(0) (mod 999983).
To make it easier, p is set to be 999983, as you see.

2
2 1 13 36
3 1 14 49 36

YES

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;
typedef long long LL;
const LL MOD = 999983;

vector<LL> p[505];
int T;

LL quick_mod(LL a,LL b,LL m)
{
LL ans = 1;
a %= m;
while(b)
{
if(b&1)
{
ans = ans*a%m;
b--;
}
b>>=1;
a=a*a%m;
}
return ans;
}

vector<LL> poly_gcd(vector<LL> a,vector<LL> b)
{
if(b.size() == 0) return a;
int t = a.size() - b.size();
vector<LL> c;
for(LL i=0; i<=t; i++)
{
LL tmp = a[i] * quick_mod(b[0],MOD-2,MOD) % MOD;
for(LL j=0; j<b.size(); j++)
a[i+j] = (a[i+j] - tmp * b[j] % MOD + MOD) % MOD;
}
LL p = -1;
for(LL i=0; i<a.size(); i++)
{
if(a[i] != 0)
{
p=i;
break;
}
}
if(p >= 0)
for(LL i=p; i<a.size(); i++)
c.push_back(a[i]);
return poly_gcd(b,c);
}

bool Import()
{
LL n,t;
if(scanf("%d",&T) == 1)
{
for(LL i=0;i<T;i++)
{
p[i].clear();
scanf("%I64d",&n);
for(LL j=0;j<=n;j++)
{
scanf("%I64d",&t);
p[i].push_back(t);
}
}
return true;
}
return false;
}

void Work()
{
if(T==1)
{
if(p[0].size() > 1) puts("YES");
else puts("NO");
return;
}
vector<LL> v = poly_gcd(p[0],p[1]);
LL i = 2;
while(i < T && v.size() > 1)
{
v = poly_gcd(v,p[i]);
i++;
}
if(v.size() > 1) puts("YES");
else puts("NO");
}

int main()
{
while(Import())
Work();
return 0;
}


1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!

3. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的