HDU3892(多项式域欧几里德算法)

2019-04-13 16:16发布

站内文章 / 模拟电子
13546 0 1296
题目：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 #include #include #include #include using namespace std; typedef long long LL; const LL MOD = 999983; vector 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 poly_gcd(vector a,vector b) { if(b.size() == 0) return a; int t = a.size() - b.size(); vector 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= 0) for(LL i=p; i 1) puts("YES"); else puts("NO"); return; } vector 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; }
 

热门文章