题目链接:https://vjudge.net/PRoblem/UVA-10951 ———————————————————————–.
UVA的都是pdf ,复制粘贴不方便 去https://vjudge.net/problem/UVA-10951看吧
————————————————————————.
题目大意: 就是给你两个多项式,让你求解两个多项式的gcd ,其中系数对n去摸,且最高次幂的系数为1.
解题思路; 还是当做正常的gcd来做,这样的话,还是经典的欧几里得算法
template<typename T>inline T _gcd(T a,T b){ return (b==0)?a:_gcd(b,a%b);}那么这个问题就转化为如何对多项式取模。 这个很容易了,注意其中用逆元来计算除法就行了
多项式取模
附本题代码 —————————————————————-。
#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;}新闻热点
疑难解答
