首页 > 其他分享 >整数域上的多项式辗转相除

整数域上的多项式辗转相除

时间:2023-05-31 16:33:06浏览次数:40  
标签:int 多项式 辗转 相除 vector ans include size


题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1892

 

题意:求两个多项式的最大的公共多项式。

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;

int MOD;
vector<int> A,B;

int quick_mod(int a,int b,int m)
{
    int ans = 1;
    a %= m;
    while(b)
    {
        if(b&1)
        {
            ans = ans*a%m;
            b--;
        }
        b>>=1;
        a=a*a%m;
    }
    return ans;
}

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] * quick_mod(b[0],MOD-2,MOD) % MOD;
        for(int j=0;j<b.size();j++)
            a[i+j] = (a[i+j] - tmp * b[j] % MOD + MOD) % MOD;
    }
    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);
}

bool Import()
{
    scanf("%d",&MOD);
    if(MOD == 0) return false;
    int n,m,t;
    A.clear();
    B.clear();
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
    {
        scanf("%d",&t);
        A.push_back(t);
    }
    scanf("%d",&m);
    for(int i=0;i<=m;i++)
    {
        scanf("%d",&t);
        B.push_back(t);
    }
    return true;
}

void Work()
{
    vector<int> v = poly_gcd(A,B);
    printf("%d",v.size()-1);
    int t = v[0];
    for(int i=0;i<v.size();i++)
    {
        v[i] = v[i] * quick_mod(t,MOD-2,MOD) % MOD;
        printf(" %d",v[i]);
    }
    puts("");
}

int main()
{
    int tt = 1;
    while(Import())
    {
        printf("Case %d: ",tt++);
        Work();
    }
    return 0;
}

 

标签:int,多项式,辗转,相除,vector,ans,include,size
From: https://blog.51cto.com/u_16146153/6388126

相关文章

  • 多项式回归模型(Office Prices)
     分析:还是上次的房价预测题目,指明要用多项式回归拟合。在多元多项式拟合时候,目标函数表示如下         对其目标函数求偏导得到         很容易写出代码。代码:#coding:utf-8importmathclassData: def__init__(self): self.x=[] self.y=0.0d......
  • 辗转相除法的证明
    描述给出两个整数a和b,请计算a和b的最大公约数,通过print语句输出。 样例评测机将通过执行命令pythonmain.py{a}{b}来执行你的代码,并将a和b作为命令行参数传入。样例一当a=15,b=12时,程序执行打印出的结果为:3样例二当a=10,b=7时,程序执行打印出的结果为......
  • 基于FPGA的LFSR16位伪随机数产生算法实现,可以配置不同的随机数种子和改生成多项式,包
    1.算法仿真效果vivado2019.2仿真结果如下:2.算法涉及理论知识概要LFSR(线性反馈移位寄存器)提供了一种在微控制器上快速生成非序列数字列表的简单方法。生成伪随机数只需要右移操作和XOR操作。LFSR完全由其多项式指定。例如,6千-次多项式与每个项存在用方程x表示6+x5+x4+x3......
  • 小灰灰机器学习day3——多项式拟合(最高项系数为2)
    importnumpyasnpTime=np.array([1,2,4,8,16,32,64])Temp=np.array([0,1,2,3,4,5,6])importmatplotlib.pyplotaspltplt.figure()plt.plot(Time,Temp,'bo')plt.xlabel("Time")plt.ylabel("Temp")plt.title(�......
  • 一元多项式的乘法与加法运算
    设计函数分别求两个一元多项式的乘积与和。输入格式:输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。输出格式:00。输入样例:434-5261-203520-7431输出样例:1......
  • 辗转相除法求最大公因数
    #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;inta,b;//辗转相除法求最大公因数intgcd(inta,intb){if(b==0)returna;returngcd(b,a%b);}intmain(){cin>&......
  • day 36 多项式之和
     1.有数组a,a[i+1]=a[i]/(i+1);2.有数组b,b[i+1]=b[i]+a[i+1];3.输出b[49];  #include<iostream>usingnamespacestd;intmain(void){doublea[50],b[50];a[0]=b[0]=1;for(inti=0;i<50;i++){a[i+1]=a[i]/(i+1);b[i+1]=b[i]+a[i+1];......
  • 多项式求和
    一问题描述输出50以内的阶乘的分数相加。二设计思路想通过循环将每项多项式求出并且给数组付初值,然后再通过循环依次相加。三程序流程图 四伪代码实现#include<bits/stdc++.h>;usingnamespacestd;intmain(){doublesum=1,Sum=0;doublea[50];for(inti=0;i<50;i++)......
  • 学习记录:NC16622[NOIP2009]多项式输出
    题目链接:https://ac.nowcoder.com/acm/problem/16622解题思路:这题有个在拓扑序上的直觉。(并不完全是拓扑学,只是一种感觉)举个例子,每i项,都是有了符号,再有系数,最后指数,我们确定了前面输出什么才有后面的判断。但并不完全是这样,该题当指数为0时,会影响系数的输出格式(x是否要输出......
  • 智能车基于五次多项式的智能车横向避幢模型,首先根据工况计算出预碰撞时间,进而计算出最
    智能车基于五次多项式的智能车横向避幢模型,首先根据工况计算出预碰撞时间,进而计算出最小转向距离,通过MPC预测控制算法来对规划路径进行跟踪控制。ID:3280675085193208......