精华内容
下载资源
问答
  • 几乎没有调用内置函数,除了求多项式最高次数时用了一下 Exponent[] (*解析多项式*) (*将f=a0+a1*x+...+an*x^n解析成{{a0,0},{a1,1},...,{an,n}}的形式*) polyCoefficients[f_] := Module[{ rules1 = { c_*base_^...

    几乎没有调用内置函数,除了求多项式最高次数时用了一下 Exponent[]

    (*解析多项式*)
    (*将f=a0+a1*x+...+an*x^n解析成{{a0,0},{a1,1},...,{an,n}}的形式*)
    polyCoefficients[f_] := Module[{
       rules1 = {
         c_*base_^power_ -> {c, power},
         base_^power_ -> {1, power},
         c_*x_ -> {c, 1},
         c_ /; NumberQ[c] -> {c, 0},
         x_ /; AtomQ[x] -> {1, 1}},
       g = If[Head[f] === Plus, f, List[Expand[f]]]},
      Replace[List @@ g, rules1, 1]]
    
    (*把解析出来的列表还原成多项式*)
    toPolynomial[list_List] := 
     Sum[list[[i, 1]]*x^list[[i, 2]], {i, Length[list]}]
    
    (*两个多项式 "相除"*)
    divide[f_, g_] := 
     Module[{cf = polyCoefficients[f], cg = polyCoefficients[g], lf, lg, 
       p},
      lf = cf[[-1]]; lg = cg[[-1]];
      p = {{lf[[1]]/lg[[1]], lf[[2]] - lg[[2]]}};
      {toPolynomial[p], Simplify[f - g*toPolynomial[p]]}]
    
    (*多项式的带余除法*)
    (*对polyQuotient[f,g],输出{d,r}满足f=g*d+r且degree(r)<degree(g)*)
    polyQuotient[f_, g_] := Module[{q = 0, r = f, d = 0},
      While[Exponent[r, x] >= Exponent[g, x],
       {q, r} = Expand[divide[r, g]];
       d = d + q;
       ];
      {d, r}]
    

    简单验证:

    [In]:=
    f = x^7 + 6 x^5; g = x^3 + x;
    {u, r} = polyQuotient[f, g]
    u*g + r // Expand
    
    [Out]=
    {-5 + 5 x^2 + x^4, 5 x}
    6 x^5 + x^7
    
    展开全文
  • 一元多项式带余除法

    千次阅读 2018-01-21 02:04:46
    多项式的度 定义 非零多项式 f(x)=∑ni=0aixif \left (x \right ) = \sum _{i = 0} ^ {n} a_i x^i (其中首项 an≠0 a_n \neq 0 )的度 deg(f(x))=n \deg \left (f \left (x \right ) \right ) = n 性质 f...

    多项式的度

    定义

    非零多项式 f(x)=ni=0aixi (其中首项 an0 )的度 deg(f(x))=n

    性质

    1. f(x)0,g(x)0deg(f(x)g(x))=deg(f(x))+deg(g(x))
    2. f(x)0,g(x)0,f(x)+g(x)0deg(f(x)+g(x))max{deg(f(x)),deg(g(x))}
    3. deg(f(x))=0f(x) 是非零常数。

    多项式运算的性质

    1. f(x)+g(x)=g(x)+f(x)
    2. [f(x)+g(x)]+h(x)=f(x)+[g(x)+h(x)]
    3. f(x)g(x)=g(x)f(x)
    4. [f(x)g(x)]h(x)=f(x)[g(x)h(x)]
    5. f(x)[g(x)+h(x)]=f(x)g(x)+f(x)h(x)
    6. f(x)0,f(x)g(x)=f(x)h(x)g(x)=h(x)
      证明:
      f(x)g(x)=f(x)h(x)f(x)[g(x)h(x)]=0
      由于 f(x)0, 因此若 g(x)h(x) g(x)h(x)0,
      于是 f(x)[g(x)h(x)]0, f(x)[g(x)h(x)]=0 矛盾。

    带余除法

    设多项式 g(x)0, 则对于任意一个多项式 f(x), 存在多项式 q(x),r(x),
    使得 f(x)=q(x)g(x)+r(x),
    其中 r(x)=0 deg(r(x))<deg(g(x))
    q(x),r(x) 是唯一的。

    证明

    存在性

    f(x)=0, f(x)=0=0g(x)+0 。命题成立。
    下面只考虑 f(x)0 的情况。
    假设对于任意一个多项式 f(x), deg(f(x))<n 时命题成立。
    deg(f(x))=n 时,令 m=deg(g(x))
    1. 若 n<m, f(x)=0g(x)+f(x) 。命题成立。
    2. 若 nm, f(x)=ni=0aixi,g(x)=mi=0bixi,
    f(x)anb1mxnmg(x)
    =ni=0aixianb1mxnmmi=0bixi
    =ni=0aixianb1mmi=0bixi+nm
    =ni=0aixianb1mni=nmbi(nm)xi
    =n1i=0aixianb1mn1i=nmbi(nm)xi
    =n1i=0(aici)xi,
    其中 ci={anb1mbi(nm),0,nmin1,0i<nm,
    因此 f(x)anb1mxnmg(x)=0 deg(f(x)anb1mxnmg(x))<n,
    于是存在多项式 q(x),r(x), 使得
    f(x)anb1mxnmg(x)=q(x)g(x)+r(x),
    其中 r(x)=0 deg(r(x))<deg(g(x))
    因此 f(x)=[anb1mxnm+q(x)]g(x)+r(x) 。命题成立。

    唯一性

    设存在多项式 q(x),r(x) 同样满足条件,则
    f(x)=q(x)g(x)+r(x)=q(x)g(x)+r(x)[q(x)q(x)]g(x)=r(x)r(x)
    q(x)q(x), [q(x)q(x)]g(x)0 deg([q(x)q(x)]g(x))=deg(q(x)q(x))+deg(g(x))deg(g(x)),
    于是 r(x)r(x)0 deg(r(x)r(x))=deg([q(x)q(x)]g(x))deg(g(x))
    但是 r(x)=0 deg(r(x))<deg(g(x)),
    r(x)=0 deg(r(x))<deg(g(x)),
    因此 deg(r(x)r(x))<deg(g(x)), deg(r(x)r(x))deg(g(x)) 矛盾。
    因此 q(x)=q(x), 于是 r(x)=r(x)

    展开全文
  • 设$f(x)$和$g(x)$是$F[x]$的任意两个多项式,并且$g(x)\neq 0$.那么在$F[x]$中可以找到多项式$q(x)$和$r(x)$,使\begin{equation}f(x)=g(x)q(x)+r(x)\end{equation}这里或者$r(x)=0$,或者$r(x)$的次数小于$g(x)$的...

    设$f(x)$和$g(x)$是$F[x]$的任意两个多项式,并且$g(x)\neq 0$.那么在$F[x]$中可以找到多项式$q(x)$和$r(x)$,使
    \begin{equation}
    f(x)=g(x)q(x)+r(x)
    \end{equation}
    这里或者$r(x)=0$,或者$r(x)$的次数小于$g(x)$的次数.满足以上条件的多项式$q(x)$和$r(x)$只有一对.


    证明:先证存在性.设$f(x)$的次数为$m(m\geq 0)$.$g(x)$的次数为$n(n\geq 0)$.若$m<n$,则令$q(x)=0,r(x)=f(x)$.当$m\geq n$,则$m> 0$.令$f(x)=a_mx^m+\Delta_1(a_m\neq 0)$.$g(x)=b_nx^n+\Delta_2(b_n\neq 0)$.则$$f(x)=\frac{a_m}{b_n}x^{m-n}g(x)+\Delta_1-\Delta_2\frac{a_m}{b_n}x^{m-n}$$
    如果多项式$\Delta_1-\Delta_2\frac{a_m}{b_n}x^{m-n}$的次数小于$g(x)$的次数,则我们令$\frac{a_m}{b_n}x^{m-n}=q(x),r(x)=\Delta_1-\Delta_2\frac{a_m}{b_n}x^{m-n}$.如果多项式$\Delta_1-\Delta_2\frac{a_m}{b_n}x^{m-n}$的次数大于或等于$g(x)$的次数,则把$\Delta_1-\Delta_2\frac{a_m}{b_n}x^{m-n}$看作新的$f(x)$继续上述过程.最终我们总能得到(1)的形式.

     


    下面证明唯一性.若存在另一组$q'(x),r'(x)$,使得
    \begin{equation}
    f(x)=g(x)q'(x)+r'(x)
    \end{equation}
    则$g(x)(q(x)-q'(x))+r(x)-r'(x)=0$.因为$g(x)\neq 0$,所以只能是$q(x)-q'(x)=0$且$r(x)-r'(x)=0$.则$g(x)=g'(x),r(x)=r'(x)\Box$

     

    转载于:https://www.cnblogs.com/yeluqing/archive/2012/10/29/3827864.html

    展开全文
  • 多项式带余除法

    链接

    点击跳转

    题解

    多项式除法戳这

    假设一个多项式 A ( x ) A(x) A(x)的最高次数为 n n n,那么我定义这个多项式的反转为 A R ( x ) = x n A ( 1 x ) A_R(x) = x^nA(\frac{1}{x}) AR(x)=xnA(x1),说白了就是把系数反过来

    F ( x ) = Q ( x ) G ( x ) + R ( x ) x n F ( 1 x ) = x n − m Q ( 1 x ) x m G ( 1 x ) + x n R ( 1 x ) F R ( x ) ≡ Q R ( x ) G R ( x ) ( m o d    x n − m + 1 ) Q R ( x ) ≡ G R − 1 ( x ) F R ( x ) ( m o d    x n − m + 1 ) F(x)=Q(x)G(x)+R(x) \\ x^nF(\frac{1}{x}) = x^{n-m}Q(\frac{1}{x})x^{m}G(\frac{1}{x}) + x^n R(\frac{1}{x})\\ F_R(x) \equiv Q_R(x)G_R(x) (\mod x^{n-m+1})\\ Q_R(x) \equiv G^{-1}_R(x)F_R(x) (\mod x^{n-m+1}) F(x)=Q(x)G(x)+R(x)xnF(x1)=xnmQ(x1)xmG(x1)+xnR(x1)FR(x)QR(x)GR(x)(modxnm+1)QR(x)GR1(x)FR(x)(modxnm+1)

    这样就可以求出 Q R ( x ) Q_R(x) QR(x)了,进而求出 Q ( x ) Q(x) Q(x),然后代入最初的式子求出 R ( x ) R(x) R(x)

    代码

    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define iinf 0x3f3f3f3f
    #define linf (1ll<<60)
    #define eps 1e-8
    #define maxn 1000010
    #define maxe 1000010
    #define cl(x) memset(x,0,sizeof(x))
    #define rep(i,a,b) for(i=a;i<=b;i++)
    #define drep(i,a,b) for(i=a;i>=b;i--)
    #define em(x) emplace(x)
    #define emb(x) emplace_back(x)
    #define emf(x) emplace_front(x)
    #define fi first
    #define se second
    #define de(x) cerr<<#x<<" = "<<x<<endl
    using namespace std;
    using namespace __gnu_pbds;
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    ll read(ll x=0)
    {
        ll c, f(1);
        for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
        for(;isdigit(c);c=getchar())x=x*10+c-0x30;
        return f*x;
    }
    #define mod 998244353ll
    struct EasyMath
    {
        ll prime[maxn], phi[maxn], mu[maxn];
        bool mark[maxn];
        ll fastpow(ll a, ll b, ll c)
        {
            ll t(a%c), ans(1ll);
            for(;b;b>>=1,t=t*t%c)if(b&1)ans=ans*t%c;
            return ans;
        }
        void exgcd(ll a, ll b, ll &x, ll &y)
        {
            if(!b){x=1,y=0;return;}
            ll xx, yy;
            exgcd(b,a%b,xx,yy);
            x=yy, y=xx-a/b*yy;
        }
        ll inv(ll x, ll p)  //p是素数
        {return fastpow(x%p,p-2,p);}
        ll inv2(ll a, ll p)
        {
            ll x, y;
            exgcd(a,p,x,y);
            return (x+p)%p;
        }
        void shai(ll N)
        {
            ll i, j;
            for(i=2;i<=N;i++)mark[i]=false;
            *prime=0;
            phi[1]=mu[1]=1;
            for(i=2;i<=N;i++)
            {
                if(!mark[i])prime[++*prime]=i, mu[i]=-1, phi[i]=i-1;
                for(j=1;j<=*prime and i*prime[j]<=N;j++)
                {
                    mark[i*prime[j]]=true;
                    if(i%prime[j]==0)
                    {
                        phi[i*prime[j]]=phi[i]*prime[j];
                        break;
                    }
                    mu[i*prime[j]]=-mu[i];
                    phi[i*prime[j]]=phi[i]*(prime[j]-1);
                }
            }
        }
        ll CRT(vector<ll> a, vector<ll> m) //要求模数两两互质
        {
            ll M=1, ans=0, n=a.size(), i;
            for(i=0;i<n;i++)M*=m[i];
            for(i=0;i<n;i++)(ans+=a[i]*(M/m[i])%M*inv2(M/m[i],m[i]))%=M;
            return ans;
        }
    }em;
    struct NTT
    {
        ll n, R[maxn];
        void init(ll bound)    //bound是积多项式的最高次幂
        {
            ll L(0);
            for(n=1;n<=bound;n<<=1,L++);
            for(ll i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
        }
        void ntt(ll* a, int opt)
        {
            ll i, j, k, wn, w, x, y, inv(em.fastpow(n,mod-2,mod));
            for(i=0;i<n;i++)if(i>R[i])swap(a[i],a[R[i]]);
            for(i=1;i<n;i<<=1)
            {
                if(opt==1)wn=em.fastpow(3,(mod-1)/(i<<1),mod);
                else wn=em.fastpow(3,(mod-1-(mod-1)/(i<<1)),mod);
                for(j=0;j<n;j+=i<<1)
                    for(w=1,k=0;k<i;k++,w=w*wn%mod)
                    {
                        x=a[k+j], y=a[k+j+i]*w%mod;
                        a[k+j]=(x+y)%mod, a[k+j+i]=(x-y)%mod;
                    }
            }
            if(opt==-1)for(i=0;i<n;i++)(a[i]*=inv)%=mod;
        }
    }ntt;
    struct Formal_Power_Series_inv
    {
        ll a[maxn], b[maxn], n, A[maxn], B[maxn];
        void run()
        {
            ll i, now, N;
            ntt.init(n), N=ntt.n;
            cl(A), cl(B), cl(b);
            b[0]=em.inv(a[0],mod);
            for(now=2;now<=N;now<<=1)
            {
                rep(i,0,now-1)A[i]=a[i], B[i]=b[i];
                ntt.init(2*now-1);
                ntt.ntt(A,1), ntt.ntt(B,1);
                rep(i,0,ntt.n-1)B[i]=B[i]*B[i]%mod*A[i]%mod;
                ntt.ntt(B,-1);
                rep(i,0,now-1)b[i]=(2*b[i]-B[i])%mod;
            }
        }
    }fpsi;
    ll f[maxn], q[maxn], g[maxn], r[maxn], a[maxn], b[maxn];
    int main()
    {
        ll i, n=read(), m=read();
        rep(i,0,n)f[i]=read();
        rep(i,0,m)g[i]=read();
        reverse(f,f+n+1), reverse(g,g+m+1);
        fpsi.n=n-m;
        rep(i,0,n-m)q[i]=f[i], fpsi.a[i]=g[i];
        fpsi.run();
        ntt.ntt(q,1), ntt.ntt(fpsi.b,1); rep(i,0,ntt.n-1)(q[i]*=fpsi.b[i])%=mod; ntt.ntt(q,-1);
        reverse(q,q+(n-m+1));
        rep(i,0,n-m)printf("%lld ",(q[i]+mod)%mod); putchar(10);
        rep(i,n-m+1,ntt.n-1)q[i]=0;
        reverse(f,f+n+1), reverse(g,g+m+1);
        ntt.init(n); ntt.ntt(q,1), ntt.ntt(g,1);
        rep(i,0,ntt.n-1)(q[i]*=g[i])%=mod;
        ntt.ntt(q,-1);
        rep(i,0,n-1)r[i]=(f[i]-q[i]+mod)%mod;
        rep(i,0,m-1)printf("%lld ",r[i]);
        return 0;
    }
    
    展开全文
  • 多项式的乘除法

    2019-01-24 21:00:33
    与上一期多项式的加法与减法相同,这期的乘除法也使用数组来操作。 关于用数组表示:就是用数组将多项式的各个系数存储起来(以常数项为第一个元素) 如 x³+x²-1 ,对应数组为 double A[] = {-1,0,1,1}; 一、...
  • 小弟初学数据结构,试着写了一个链表实现一元多项式运算,但是写到除法时程序动不动就死了[img=https://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/9.gif][/img],下面是我写的部分代码,有大佬能...
  • 一.一元多项式环 二.整除关系与带余除法 三.最大公因式
  • 现在给出 nnn 次多项式 A(x)A(x)A(x) 和 mmm 次多项式 B(x)B(x)B(x),求出它们的商 C(x)C(x)C(x) 和余数 D(x)D(x)D(x)。也就是说,找出 n−mn-mn−m 次多项式 C(x)C(x)C(x) 和次数小于 mmm 的多项式 D(x)D(x)D(x) ...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼所谓的模2整系数多项式就是系数是整数,并且,只能是0, 1的多项式,即所有系数是模2(mod 2)的整数每个多项式,按照多项式每项的幂对应2进制的幂,一一对应加起来可以对应...
  • 多项式除法

    2012-04-27 17:30:25
    本程序是依据欧几里得算法计算多项式除法的程序; 程序的目的是计算有限域上的多项式除法,所以本程 序只在除数多项式首项系数为1的情况下可以正确求解。 要使得本程序可以通用,需要将Node结构体的系数coff ...
  • 这个除法是带余除法,所以并不能直接求逆解决。 要求的就是给定两个多项式$A(x),B(x)$,其项数为$n,m$ 求解一个$n-m$项的多项式$C(x)$,以及一个小于$n-m$项的多项式$R(x)$。 满足:$A(x)=B(x)*C(x)+R(x)$。 定义一...
  • 二、多项式除法 更为一般性的推导,p(X)为被除式,q(X)为商式,r(X)为式。不妨假设gn-k=1。 若被除式p(X)中Xn-k的系数为1,此时q(X)=1;r(X)=p(X)-g(X)=p(X)+g(X) 若被除式p(X)中Xn-k的系数为0,此时q(X)=...
  • 多项式除法

    千次阅读 2019-03-27 13:39:39
    多项式除法 多项式看起来像这样: 多项式例子 这个多项式有 3 项 除法 有时候可以这样做多项式除法。 但有时用 "长除" 会比较合适(与数字长除法相似) 分子和分母 每部分的多项式有都有名字: ...
  • 一元多项式除法

    2011-10-12 21:11:57
    数据结构中的一元多项式除法,用单向链表实现,也涉及到一元多项式的加法等等。
  • Java 多项式除法

    千次阅读 2017-08-27 09:16:31
    多项式除法代码实现: import java.text.DecimalFormat; public class duoxiangshichufa_div { static void poly_div(double A[],int m,double B[],int n,double R[],int k,double L[],int l){ int i,j,mm,ll; ...
  • #include #include #include ...//f,g,h存储的是多项式的系数,sum存储的是f*g的系数以及最后余数的系数 int f[maxn],g[maxn],h[maxn],sum[maxn]; int lf,lg,lh,ls;//分别为f,g,h,sum的最高次幂
  • 多项式除法

    2021-04-01 21:40:39
    你需要计算两个多项式相除的商Q和R,其中R的阶数必须小于B的阶数。 输入格式: 输入分两行,每行给出一个非零多项式,先给出A,再给出B。每行的格式如下: N e[1] c[1] … e[N] c[N] 其中N是该多项式非零项的个数...
  • 多项式求逆与多项式除法/取模

    千次阅读 2018-10-17 08:04:33
    多项式求逆是多项式模块中的一个重要操作(“操作”这个词看出如今多项式题是多么的工业化,犹如毒瘤8操作LCT),在做生成函数/多项式除法多项式取模/多项式多点求值中均有应用 对于一个n次多项式F(x)F(x)F(x),...
  • 2.带余除法 初等数论 2.带余除法2.带余除法2.带余除法
  • 多项式的)因式分解...0. 多项式除法(Polynomial long division)Polynomial long division - Wikipedia 1. 因式分解定理Factor theorem该定理表达的是,多项式 f(x)f(x) 存在因子 x−kx-k 当且仅当 f(k)=0f(k
  • 循环冗余校验码(Cyclic Redundancy Check,CRC)是数据通信领域中最常用的一种差错校验码,该校验方法中,使用【多项式除法】,也就是【模2除法】运算后的余数为校验字段。 如数据信息为n位,则将其左移k位后,被...
  • C++多项式除法的探讨

    2020-01-02 10:15:26
    最近的一项工作就是用vector实现多项式类,这个类需要完成多项式的数据结构的定义以及基本运算,包括加减乘除,前三个还比较容易,对于多项式除法,因为有除不尽的情况,比如: 计算 其结果是: 明显是除...
  • 多项式的乘法和除法

    2019-02-08 22:14:23
    多项式乘法 /* 多项式乘法:多项式P(m)系数保存在p数组中,多项式Q(n)系数保存在q数组中 结果最高次数为m+n,共m+n+1项 ai bj的乘积应累加到结果i+j项对应的系数中 */ #include &lt;stdio.h&gt; int ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,175
精华内容 2,070
关键字:

多项式带余除法