UVA - 10951 Polynomial GCD 【最大公共多项式】

不念不忘少年蓝@ 2023-07-03 04:54 5阅读 0赞

**Disctiption**  
Given a decimal integer number you will have to find out how many trailing zeros will be there in its  
factorial in a given number system and also you will have to find how many digits will its factorial have  
in a given number system? You can assume that for a b based number system there are b different  
symbols to denote values ranging from 0 . . . b − 1.

**Input**  
There will be several lines of input. Each line makes a block. Each line will contain a decimal number  
N (a 20bit unsigned number) and a decimal number B (1 < B ≤ 800), which is the base of the number  
system you have to consider. As for example 5! = 120 (in decimal) but it is 78 in hexadecimal number  
system. So in Hexadecimal 5! has no trailing zeros.

**Output**  
For each line of input output in a single line how many trailing zeros will the factorial of that number  
have in the given number system and also how many digits will the factorial of that number have in  
that given number system. Separate these two numbers with a single space. You can be sure that the  
number of trailing zeros or the number of digits will not be greater than 231 − 1.

**Sample Input**  
2 10  
5 16  
5 10

**Sample Output**  
0 1  
0 2  
1 3

**题意**  
给定两个多项式，求塔恩两个的最大公共多项式。

**思路**  
跟求最大公因子思路相似。  
套了个板子。  
[求最大公共多项式][Link 1]

**AC代码**

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    vector<int>G[100010],ans;
    int n;
    int a, b;
    
    ll qmi(ll m, ll k, ll mod)
    { 
        ll res = 1 % mod, t = m;
        while (k)
        { 
            if (k&1)
                res = res * t % mod;
            t = t * t % mod;
            k >>= 1;
        }
        return res;
    }
    
    vector<int> poly_gcd(vector<int> a,vector<int> b)
    { 
        if (b.size() == 0)
            return a;
        int t = a.size() - b.size();
        vector<int> c;
        for (int i=0; i<=t; i++)
        { 
            int tmp=a[i]*qmi(b[0],n-2,n)%n;
            for(ll j=0; j<b.size(); j++)
                a[i+j]=(a[i+j]-tmp*b[j]%n+n)%n;
        }
        int p=-1;
        for(int i=0; i<a.size(); i++)
        { 
            if(a[i]!=0)
            { 
                p=i;
                break;
            }
        }
        if(p>=0)
        { 
            for(int i=p; i<a.size(); i++)
                c.push_back(a[i]);
        }
        return poly_gcd(b,c);
    }
    
    int main()
    { 
        int cas=1;
        while(scanf("%d", &n)!=EOF)
        { 
            if(n==0)
                return 0;
            G[0].clear();
            G[1].clear();
            for(int i=0; i<2; i++)
            { 
                scanf("%d", &a);
                for (int j=0; j<=a; j++)
                { 
                    scanf("%d", &b);
                    G[i].push_back(b);
                }
            }
            ans=poly_gcd(G[0], G[1]);
            printf("Case %d: %d", cas, ans.size()-1);
            int tmp=qmi(ans[0], n-2,n);
            for(int i=0; i<ans.size(); i++)
            { 
                ans[i]=ans[i]*tmp%n;
                printf(" %d", ans[i]);
            }
            printf("\n");
            cas++;
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43460224/article/details/104145933