HDU3892 Common Roots 多项式欧几里德求最大公共多项式 - c++编程基础

这就是数论坑的地方了把，有些题目真心偏到你无法想象，需要用到多项式欧几里德求多项式的最大公共多项式

题意：给你n个多项式，问他们有没有共同的根

先分析把，假设有多项式a,b,同时又有多项式k,r，令 a = k*b +r,应题目要求，令解为0，那么a = 0,同时b也要等于0，那么这时候要满足a=b=0 其实 r = 0,这时候就不需要去管k了，有没有发现跟那个扩展欧几里德有点相似的方程，这时候分析一下,肯定跟a,b,r有关系，同时因为他们有共同的根，所以可以把问题转化成b,r的问题了，这时候问题就转化成求几个多项式的最大公约数，其实这是个错误名称，应该是求多项式的最大公共多项式

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                  > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; vector
                    
                      G[1000 + 5]; const int MOD = 999983; int k; int num[1000 + 5][50 + 5]; void clear() { for(int i=0;i
                     
                      >= 1; a = a * a%MOD; } return ans; } /*多项式求最大公共项*/ vector
                      
                        poly_gcd(vector
                       
                         a,vector
                        
                          b) { if(b.size() == 0) return a; int t = a.size() - b.size(); vector
                         
                           c; for(int i=0;i<=t;i++) { ll tmp = a[i] * quick(b[0],MOD-2)%MOD; for(ll j=0;j
                          
                           = 0) { for(ll i=p;i
                           
                             1) puts(YES); else puts(NO); continue; } vector
                            
                              g = poly_gcd(G[0],G[1]); for(ll i=2;i
                             
                               1) puts(YES); else puts(NO); } return 0; }