題目：http://acm.hdu.edu.cn/showproblem.php?pid=3892

?

題意：給出n個多項式，如果它們模999983等于0的所有根中有相同的就輸出“YES”，否則輸出“NO”。

?

分析：假設有多項式a和多項式b，如果a = q*b + r，假設a和b有公共的根x，則取x的時候，a = q*b +?r = 0且b = 0.

所以此時r也等于0. 所以a， b， r有同根x，這樣a，b的問題，就變成b，r的問題了。然后就是求最大公約數問題了。

?

#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; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的HDU3892(多项式域欧几里德算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。