[原创]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; }
|