[原创]UVA 10951 - Polynomial GCD []【数论】
2017-03-03 19:21:28 Tabris_ 阅读数：393
博客爬取于2020-06-14 22:41:29
以下为正文
版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/60145283
题目链接:https://vjudge.net/problem/UVA-10951
-----------------------------------------------------------------------.
UVA的都是pdf ,复制粘贴不方便 去https://vjudge.net/problem/UVA-10951看吧
------------------------------------------------------------------------.
题目大意:
就是给你两个多项式,让你求解两个多项式的gcd ,其中系数对n去摸,且最高次幂的系数为1.
解题思路;
还是当做正常的gcd来做,这样的话,还是经典的欧几里得算法
1
2
3
4
| template<typename T>
inline T _gcd(T a,T b){
return (b==0)?a:_gcd(b,a%b);
}
|
那么这个问题就转化为如何对多项式取模。
这个很容易了,注意其中用逆元来计算除法就行了
多项式取模
附本题代码
----------------------------------------------------------------。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| # include <bits/stdc++.h>
using namespace std;
# define INF (~(1<<31))
# define INFLL (~(1ll<<63))
# define pb push_back
# define mp make_pair
# define abs(a) ((a)>0?(a):-(a))
# define lalal puts("*******");
# define s1(x) scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
typedef long long int LL ;
typedef unsigned long long int uLL ;
const int N = 50000+7;
const int MOD = 1e9+7;
const double eps = 1e-7;
const double Pi = acos(-1.0);
const double E = exp(1.0);
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void fre(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
template<typename T>inline T _gcd(T a,T b){return (b==0)?a:_gcd(b,a%b);}
template<typename T>inline T _lcm(T a,T b){return a/_gcd(a,b)*b;}
LL qmod(LL a,LL b,LL c){LL ret=1ll;while(b){if(b&1)ret=ret*a%c;b>>=1,a=a*a%c;}return ret;}
/***********************************************************************/
# define vi vector<int>
int n;
int inv(int x){
return qmod(x,n-2,n);
}
vi vimod(vi f,vi g){
int fz = f.size(),gz = g.size();
for(int i=0;i<fz;i++){
if(fz-i-gz < 0) break;
int a=f[i]*inv(g[0])%n;
for(int j=0;j<gz;j++){
int now=i+j;
f[now]=((f[now]-a*g[j]%n)%n+n)%n;
}
}
vi ans;
int p=-1;
for(int i=0;i<fz;i++)if(f[i]!=0){p=i;break;}
if(p>=0) for(int i=p;i<fz;i++)ans.pb(f[i]);
return ans;
}
vi gcd(vi f,vi g){
if(g.size()==0) return f;
return gcd(g,vimod(f,g));
}
vi f,g;
int main(){
int kcase = 0;
while(~scanf("%d",&n)&&n){
f.clear(),g.clear();
int d,x;
scanf("%d",&d);
for(int i=0;i<=d;i++){
scanf("%d",&x);
f.pb(x);
}
scanf("%d",&d);
for(int i=0;i<=d;i++){
scanf("%d",&x);
g.pb(x);
}
vi ans = gcd(f,g);
int tmp = inv(ans[0]);
printf("Case %d: %d",++kcase,ans.size()-1);
for(int i=0;i<ans.size();i++){
printf(" %d",ans[i]*tmp%n);
}
puts("");
}
return 0;
}
|
wechat
