UVA 10951 - Polynomial GCD

题目链接

题意：给定两个多项式，求多项式的gcd，要求首项次数为1，多项式中的运算都%n，并且n为素数.

思路：和gcd基本一样，只不过传入的是两个多项式，由于有%n这个条件，所以计算过程可以用乘法逆去计算除法模，然后最后输出的时候每项除掉首项的次数就是答案了.

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int n; vector
     
       f, g; int exgcd(int a, int b, int &x, int &y) { if (!b) {x = 1; y = 0; return a;} int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int inv(int a, int n) { int x, y; exgcd(a, n, x , y); return (x + n) % n; } vector
      
        pmod(vector
       
         f, vector
        
          g) { int fz = f.size(), gz = g.size(); for (int i = 0; i < fz; i++) { int k = fz - i - gz; if (k < 0) break; int a = f[i] * inv(g[0], n) % n; for (int j = 0; j < gz; j++) { int now = i + j; f[now] = ((f[now] - a * g[j] % n) % n + n) % n; } } vector
         
           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.push_back(f[i]); return ans; } vector
          
            gcd(vector
           
             f, vector
            
              g) { if (g.size() == 0) return f; return gcd(g, pmod(f, g)); } int main() { int cas = 0; while (~scanf("%d", &n) && n) { f.clear(); g.clear(); int a, k; scanf("%d", &a); for (int i = 0; i <= a; i++) { scanf("%d", &k); f.push_back(k); } scanf("%d", &a); for (int i = 0; i <= a; i++) { scanf("%d", &k); g.push_back(k); } vector
             
               ans = gcd(f, g); int tmp = inv(ans[0], n), ansz = ans.size();; printf("Case %d: %d", ++cas, ansz - 1); for (int i = 0; i < ansz; i++) { printf(" %d", ans[i] * tmp % n); } printf("\n"); } return 0; }