题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1892
题意:求两个多项式的最大的公共多项式。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;
int MOD;
vector<int> A,B;
int quick_mod(int a,int b,int m)
{
int ans = 1;
a %= m;
while(b)
{
if(b&1)
{
ans = ans*a%m;
b--;
}
b>>=1;
a=a*a%m;
}
return ans;
}
vector<int> poly_gcd(vector<int> a,vector<int> b)
{
if(b.size() == 0) return a;
int t = a.size() - b.size();
vector<int> c;
for(int i=0;i<=t;i++)
{
int tmp = a[i] * quick_mod(b[0],MOD-2,MOD) % MOD;
for(int j=0;j<b.size();j++)
a[i+j] = (a[i+j] - tmp * b[j] % MOD + MOD) % MOD;
}
int p = -1;
for(int i=0;i<a.size();i++)
{
if(a[i] != 0)
{
p=i;
break;
}
}
if(p >= 0)
for(int i=p;i<a.size();i++)
c.push_back(a[i]);
return poly_gcd(b,c);
}
bool Import()
{
scanf("%d",&MOD);
if(MOD == 0) return false;
int n,m,t;
A.clear();
B.clear();
scanf("%d",&n);
for(int i=0;i<=n;i++)
{
scanf("%d",&t);
A.push_back(t);
}
scanf("%d",&m);
for(int i=0;i<=m;i++)
{
scanf("%d",&t);
B.push_back(t);
}
return true;
}
void Work()
{
vector<int> v = poly_gcd(A,B);
printf("%d",v.size()-1);
int t = v[0];
for(int i=0;i<v.size();i++)
{
v[i] = v[i] * quick_mod(t,MOD-2,MOD) % MOD;
printf(" %d",v[i]);
}
puts("");
}
int main()
{
int tt = 1;
while(Import())
{
printf("Case %d: ",tt++);
Work();
}
return 0;
}
标签:int,多项式,辗转,相除,vector,ans,include,size From: https://blog.51cto.com/u_16146153/6388126