精华内容
下载资源
问答
  • 现在给出 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) ...

    文章目录

    问题

    现在给出 n n n 次多项式 A ( x ) A(x) A(x) m m m 次多项式 B ( x ) B(x) B(x),求出它们的商 C ( x ) C(x) C(x) 和余数 D ( x ) D(x) D(x)。也就是说,找出 n − m n-m nm 次多项式 C ( x ) C(x) C(x) 和次数小于 m m m 的多项式 D ( x ) D(x) D(x) 使得 A ( x ) = B ( x ) C ( x ) + D ( x ) A(x)=B(x)C(x)+D(x) A(x)=B(x)C(x)+D(x)。系数对 998244353 998244353 998244353 取模。

    思路

    先考虑求商。一个很自然的思路就是求出 B ( x ) B(x) B(x) 的乘法逆元再乘上 A ( x ) A(x) A(x),但我们发现这样求出来的结果是错误的,原因是这样的结果求出来后根本没有余数我们考虑把余数通过某种方式处理掉。
    考虑式子 A ( x ) = B ( x ) C ( x ) + D ( x ) A(x)=B(x)C(x)+D(x) A(x)=B(x)C(x)+D(x),代入 1 x \frac 1 x x1 并两端乘上 x n x^n xn,则可以得到 x n A ( 1 x ) = x n B ( 1 x ) C ( 1 x ) + x n D ( 1 x ) x^nA(\frac 1 x)=x^nB(\frac 1 x)C(\frac 1 x)+x^nD(\frac 1 x) xnA(x1)=xnB(x1)C(x1)+xnD(x1)如果有 n n n 次多项式 F ( x ) F(x) F(x)(不足 n n n 次就补 0 0 0),不难发现把 F ( 1 x ) F(\frac 1 x) F(x1) 乘上 x n x^n xn 相当于把 F ( x ) F(x) F(x) 的系数左右调转,得到的多项式记作 F R ( x ) F_R(x) FR(x)。显然,它可以 O ( n ) O(n) O(n) 求出。
    有了这个定义,上面的式子就可以简化为 A R ( x ) = B R ( x ) C R ( x ) + x n − m + 1 D R ( x ) A_R(x)=B_R(x)C_R(x)+x^{n-m+1}D_R(x) AR(x)=BR(x)CR(x)+xnm+1DR(x)
    A R ( x ) ≡ B R ( x ) C R ( x )   ( mod  x n − m + 1 ) A_R(x)\equiv B_R(x)C_R(x)\ (\text{mod}\ x^{n-m+1}) AR(x)BR(x)CR(x) (mod xnm+1)
    这样余数的干扰就被排除,我们就可以用乘法逆元求出 C R ( x ) ≡ A R ( x ) ( B R ( x ) ) − 1   ( mod  x n − m + 1 ) C_R(x)\equiv A_R(x)(B_R(x))^{-1}\ (\text{mod}\ x^{n-m+1}) CR(x)AR(x)(BR(x))1 (mod xnm+1)这个结果恰巧为 n − m n-m nm 次多项式,再把它反过来就可以得到 C ( x ) C(x) C(x) 了。
    现在求出了 C ( x ) C(x) C(x),余数就可以用 D ( x ) = A ( x ) − B ( x ) C ( x ) D(x)=A(x)-B(x)C(x) D(x)=A(x)B(x)C(x) 求出来了。

    代码

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define re register
    #define ll long long
    using namespace std;
    ll mod=998244353,G[2]={332748118,3},inv;
    ll A[450001],B[450001],invB[450001],D[450001];
    ll f[450001],g[450001];
    int rev[450001],m,n,lenA,lenB;
    inline ll qp(ll a,int b){
    	ll res=1ll;
    	while(b){
    		if(b&1) (res*=a)%=mod;
    		(a*=a)%=mod;
    		b>>=1;
    	}
    	return res;
    }
    ll w,w_n,x,y,z;
    inline void NTT(ll *a,int flag){
    	for(re int i=1;i<n;++i){
    		if(rev[i]<i) swap(a[i],a[rev[i]]);
    	}
    	for(re int i=1;i<n;i<<=1){
    		w_n=qp(G[flag],(mod-1)/(i<<1));
    		for(re int j=0;j<n;j+=(i<<1)){
    			w=1ll; z=i+j;
    			for(re int k=j;k<z;++k){
    				x=a[k];
    				y=w*a[k+i]; if(y>=mod) y%=mod;
    				a[k]=x+y; if(a[k]>=mod) a[k]-=mod;
    				a[k+i]=x-y; if(a[k+i]<0) a[k+i]+=mod;
    				w*=w_n; if(w>=mod) w%=mod;
    			}
    		}
    	}
    	if(!flag){
    		inv=qp(n,mod-2);
    		for(re int i=0;i<n;++i) (a[i]*=inv)%=mod;
    	}
    	return;
    }
    int main(){
    	scanf("%d%d",&lenA,&lenB);
    	for(re int i=0;i<=lenA;++i) scanf("%lld",&A[i]);
    	for(re int i=lenB;i>=0;--i) scanf("%lld",&B[i]);  //直接反过来输入
    	invB[0]=qp(B[0],mod-2);
    	for(re int i=1;i<=lenA-lenB;i<<=1){
    		n=(i<<2);
    		m+=1; memset(g,0,sizeof(g));
    		for(re int j=1;j<n;++j) rev[j]=((rev[j>>1]>>1)|((j&1)<<m));
    		for(re int j=i-1;j<(i<<1);++j) f[j]=B[j];
    		for(re int j=0;j<i;++j) g[j]=invB[j];
    		NTT(f,1); NTT(g,1);
    		for(re int j=0;j<n;++j) g[j]=(((g[j]*g[j])%mod)*f[j])%mod;
    		NTT(f,0); NTT(g,0);
    		for(re int j=i;j<(i<<1);++j) invB[j]=((invB[j]<<1)%mod-g[j]+mod)%mod;
    	}  //求乘法逆元
    	memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
    	for(re int i=0;i<=lenA-lenB;++i) f[i]=A[lenA-i];
    	for(re int i=0;i<=lenA-lenB;++i) g[i]=invB[i];
    	m=1; while((1<<m)<=((lenA-lenB)<<1)) m+=1; n=(1<<m);
    	for(re int i=1;i<n;++i) rev[i]=((rev[i>>1]>>1)|((i&1)<<(m-1)));
    	NTT(f,1); NTT(g,1);
    	for(re int i=0;i<n;++i) (f[i]*=g[i])%=mod;  //得到 C_R(x)
    	NTT(f,0);
    	for(re int i=0;i<=lenA-lenB;++i) D[i]=f[lenA-lenB-i];
    	for(re int i=0;i<=(lenB>>1);++i) swap(B[i],B[lenB-i]);
    	m=1; while((1<<m)<=lenA) m+=1; n=(1<<m);
    	for(re int i=1;i<n;++i) rev[i]=((rev[i>>1]>>1)|((i&1)<<(m-1)));
    	NTT(B,1); NTT(D,1);
    	for(re int i=0;i<n;++i) (B[i]*=D[i])%=mod;  //B(x)*D(x)
    	NTT(B,0); NTT(D,0);
    	for(re int i=0;i<=lenA-lenB;++i) printf("%lld ",D[i]);printf("\n");
    	for(int i=0;i<lenB;++i){
    		A[i]-=B[i];
    		if(A[i]<0) A[i]+=mod;  //求解余数
    	}
    	for(re int i=0;i<lenB;++i) printf("%lld ",A[i]);printf("\n");
    	return 0;
    }
    

    谢谢观看,记得点赞

    展开全文
  • 设$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

    展开全文
  • C++多项式除法的探讨

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

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

    计算

    其结果是:

    明显是除不尽的,但是按照普通的除法去做,余数就会被舍弃,当涉及到求值或者求导时,就会产生极大的误差,尤其是在实现牛顿法求解高次多项式的数值解时,需要计算迭代点的函数值以及导数值,余数的舍弃必然使函数值产生偏差,其导数值也必然不准,也就使最后产生不靠谱的结果。

    解决方案有两种思路,也是我自己的思考过程,第一种,我想通过指针的形式将多项式除法的结果和余数都返回,然后在计算函数值和导数值的时候,需要将余数和除数再次相除,这样做确实可以解决问题,但是,前提是需要将被除数,除数区分开,在单次除法的计算中问题不大,但是涉及到复杂函数构成时,就显得困难了。

    所以产生了第二种解决方案,就是遇到除法,不去计算结果,而是构造一个结构体,这个结构体有两部分构成,一部分是被除数,一部分是除数,也就是变成分子分母的形式

    template<typename T>
    struct Div_Poly
    {
    	Poly<T> Numer_Poly; //分子--被除数
    	Poly<T> Denom_Poly;//分母--除数
    }
    

    在涉及除法时,就直接传值操作,而不进行实际的除法运算,求函数值时直接将函数值代入,求导数值时,利用导数的定义

     

    进行计算。

    delta_x可以设置为double类型的极小值,比如可以取 0.00000001,自己把握精度。

    这部分代码我将传到的github上

    Poly_class_based_on_vector

    文件为demo_4.1.zip

    其他为早期版本。

    展开全文
  • 一.一元多项式环 二.整除关系与带余除法 三.最大公因式

    一.一元多项式环(7.1)
    1.一元多项式
    (1)一元多项式的定义:
    在这里插入图片描述
    (2)一元多项式的次数:
    在这里插入图片描述
    (3)一元多项式的运算:
    在这里插入图片描述
    在这里插入图片描述

    另外,可以证明 K [ x ] K[x] K[x]是数域 K K K上的1个线性空间, K [ x ] K[x] K[x]的1个基是 { 1 , x , x 2 . . . } \{1,x,x^2...\} {1,x,x2...}
    在这里插入图片描述

    (4)一元多项式的和与积的次数:

    命题1:设 f ( x ) , g ( x ) ∈ K [ x ] f(x),g(x)∈K[x] f(x),g(x)K[x],则 d e g ( f ( x ) ± g ( x ) ) ≤ m a x { d e g   f ( x ) , d e g   g ( x ) } ( 5 ) d e g ( f ( x ) g ( x ) ) = d e g   f ( x ) + d e g   g ( x ) ( 6 ) deg(f(x)±g(x))≤max\{deg\,f(x),deg\,g(x)\}\qquad(5)\\deg(f(x)g(x))=deg\,f(x)+deg\,g(x)\qquad(6) deg(f(x)±g(x))max{degf(x),degg(x)}(5)deg(f(x)g(x))=degf(x)+degg(x)(6)
    在这里插入图片描述

    推论1:设 f ( x ) , g ( x ) ∈ K [ x ] f(x),g(x)∈K[x] f(x),g(x)K[x],则
    f ( x ) ≠ 0 且 g ( x ) ≠ 0 ⇒ f ( x ) g ( x ) ≠ 0 ( 7 ) f(x)≠0且g(x)≠0⇒f(x)g(x)≠0\qquad(7) f(x)=0g(x)=0f(x)g(x)=0(7)
    \quad 从而 f ( x ) g ( x ) = 0 ⇒ f ( x ) = 0 或 g ( x ) = 0 f(x)g(x)=0⇒f(x)=0或g(x)=0 f(x)g(x)=0f(x)=0g(x)=0
    K [ x ] K[x] K[x]中2个非零多项式的乘积的首项系数等于这2个多项式的首项系数的乘积

    推论2: K [ x ] K[x] K[x]中的乘法适合消去律,即 f ( x ) g ( x ) = f ( x ) h ( x ) 且 f ( x ) ≠ 0 ⇒ g ( x ) = h ( x ) f(x)g(x)=f(x)h(x)且f(x)≠0⇒g(x)=h(x) f(x)g(x)=f(x)h(x)f(x)=0g(x)=h(x)
    在这里插入图片描述

    2.环的基本概念
    在这里插入图片描述
    (1)环的定义:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    (2)常见的特殊类型的环:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    注意:整环的概念中的"无零因子"是指没有非平凡的零因子,即整环是无零因子环

    (3)环的同构:
    在这里插入图片描述

    命题2:若环 R R R到环 R ′ R' R有1个同构映射 σ σ σ,且 R R R有单位元 e e e,则 σ ( e ) σ(e) σ(e) R ′ R' R的单位元
    在这里插入图片描述

    3.子环
    (1)定义:
    在这里插入图片描述
    在这里插入图片描述
    (2)子环的判定

    命题3:环 R R R的1个非空子集 R 1 R_1 R1为1个子环的充要条件是: R 1 R_1 R1对于 R R R的减法与乘法都封闭,即 a , b ∈ R 1 ⇒ a − b ∈ R 1 且 a b ∈ R 1 a,b∈R_1⇒a-b∈R_1且ab∈R_1 a,bR1abR1abR1
    在这里插入图片描述
    注意:子环中的单位元和原环中的单位元没有确定的关系,可能子环有单位元而圆环无,也可能反过来,还可能均有单位元但二者的单位元不同,也可能均无或均有且相同

    (3)扩环:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    说明:条件2°就是说数域 K K K(也是1个环) ≅ R 1 \cong R_1 R1
    在这里插入图片描述

    4.一元多项式环 K [ x ] K[x] K[x]的通用性质
    在这里插入图片描述

    定理1:设 K K K是1个数域, R R R是1个有单位元 1 ′ 1' 1的交换环, R R R可看成是 K K K的1个扩环,其中 K K K R R R的子环 R 1 R_1 R1(含有 1 ′ 1' 1)的保持加法和乘法运算的双射(即同构映射)记作 σ σ σ;对 ∀ t ∈ R ∀t∈R tR,令 σ t : K [ x ] → R f ( x ) = ∑ i = 0 n a i x i → ∑ i = 0 n τ ( a i ) t i : = f ( t ) σ_t:K[x]→R\\f(x)=\displaystyle\sum_{i=0}^na_ix^i→\displaystyle\sum_{i=0}^nτ(a_i)t^i:=f(t) σt:K[x]Rf(x)=i=0naixii=0nτ(ai)ti:=f(t) σ t σ_t σt K [ x ] K[x] K[x] R R R的1个映射,且 σ t ( x ) = t σ_t(x)=t σt(x)=t,且 σ t σ_t σt保持加法和乘法运算,即如果在 K [ x ] K[x] K[x]中有 f ( x ) + g ( x ) = h ( x ) , f ( x ) g ( x ) = p ( x ) f(x)+g(x)=h(x),f(x)g(x)=p(x) f(x)+g(x)=h(x),f(x)g(x)=p(x)则在 R R R中有 f ( t ) + g ( t ) = h ( t ) , f ( t ) g ( t ) = h ( t ) f(t)+g(t)=h(t),f(t)g(t)=h(t) f(t)+g(t)=h(t),f(t)g(t)=h(t)映射 σ t σ_t σt称为x用t代入
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    定理意义:
    在这里插入图片描述
    关于不定元:
    在这里插入图片描述
    注意:从该定理证明 f ( t ) g ( t ) = p ( t ) f(t)g(t)=p(t) f(t)g(t)=p(t)的过程中看到,只要 R R R的元素 t t t可与 R ′ R' R的元素 τ ( a i )   ( a i ∈ K ) τ(a_i)\,(a_i∈K) τ(ai)(aiK)交换,就有此式成立,而不需要 R R R是交换环,即不需要 t 1 ∈ R t_1∈R t1R t 2 ∈ R t_2∈R t2R可交换;从而 R R R不必是交换环,只要 R R R的元素 t t t可与 R ′ R' R的元素 τ ( a i )   ( a i ∈ K ) τ(a_i)\,(a_i∈K) τ(ai)(aiK)交换,不定元 x x x就可用 t t t带入

    在这里插入图片描述
    二.整除关系与带余除法(7.2)
    在这里插入图片描述
    1.整除关系
    (1)整除的定义:
    在这里插入图片描述
    (2)整除的性质:

    从整除的定义易推出:
    0   ∣   f ( x ) ⇔ f ( x ) = 0 0\,|\,f(x)⇔f(x)=0 0f(x)f(x)=0
    在这里插入图片描述
    ②对 ∀ f ( x ) ∈ K [ x ] , f ( x )   ∣   0 ∀f(x)∈K[x],f(x)\,|\,0 f(x)K[x],f(x)0
    在这里插入图片描述
    ③对 ∀ b ∈ K ∗ , ∀ f ( x ) ∈ K [ x ] , b   ∣   f ( x ) ∀b∈K^*,∀f(x)∈K[x],b\,|\,f(x) bK,f(x)K[x],bf(x)
    在这里插入图片描述
    注: K ∗ = K − { 0 } K^*=K-\{0\} K=K{0}

    整除是集合 K [ x ] K[x] K[x]上的1个二元关系,具有
    ①反身性:对 ∀ f ( x ) ∈ K [ x ] , f ( x )   ∣   f ( x ) ∀f(x)∈K[x],f(x)\,|\,f(x) f(x)K[x],f(x)f(x)
    在这里插入图片描述
    ②传递性:在 K [ x ] 中 , K[x]中, K[x], f ( x )   ∣   g ( x ) , g ( x )   ∣   h ( x ) f(x)\,|\,g(x),g(x)\,|\,h(x) f(x)g(x),g(x)h(x),则 f ( x )   ∣   h ( x ) f(x)\,|\,h(x) f(x)h(x)
    在这里插入图片描述
    注意:整除关系不具有对称性,即从 g ( x )   ∣   f ( x ) g(x)\,|\,f(x) g(x)f(x)不能推出 f ( x )   ∣   g ( x ) f(x)\,|\,g(x) f(x)g(x)

    命题4:在 K [ x ] K[x] K[x]中,如果 g ( x )   ∣   f i ( x )   ( i = 1 , 2... s ) g(x)\,|\,f_i(x)\,(i=1,2...s) g(x)fi(x)(i=1,2...s),那么对于 ∀ u 1 ( x ) . . . u s ( x ) ∈ K [ x ] ∀u_1(x)...u_s(x)∈K[x] u1(x)...us(x)K[x],都有 g ( x )   ∣   [ u 1 ( x ) f 1 ( x ) + . . . + u s ( x ) f s ( x ) ] g(x)\,|\,[u_1(x)f_1(x)+...+u_s(x)f_s(x)] g(x)[u1(x)f1(x)+...+us(x)fs(x)]
    在这里插入图片描述

    命题5:在 K [ x ] K[x] K[x]中,若 g ( x )   ∣   f ( x ) g(x)\,|\,f(x) g(x)f(x) f ( x ) ≠ 0 f(x)≠0 f(x)=0,则 d e g   g ( x ) ≤ d e g   f ( x ) deg\,g(x)≤deg\,f(x) degg(x)degf(x)
    在这里插入图片描述
    注意:若 f ( x ) = 0 f(x)=0 f(x)=0,则该命题不成立

    (3)相伴的定义:
    在这里插入图片描述
    (4)相伴的判定:

    命题6:在 K [ x ] K[x] K[x]中, f ( x ) ∼ g ( x ) f(x)\sim g(x) f(x)g(x)当且仅当 ∃ c ∈ K ∗ ∃c∈K^* cK,使得 f ( x ) = c ⋅ g ( x ) f(x)=c·g(x) f(x)=cg(x)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    注: K ∗ = K − { 0 } K^*=K-\{0\} K=K{0}

    2.带余除法
    在这里插入图片描述
    (1)带余除法:

    定理2:设 f ( x ) , g ( x ) ∈ K [ x ] f(x),g(x)∈K[x] f(x),g(x)K[x] g ( x ) ≠ 0 g(x)≠0 g(x)=0,则在 K [ x ] K[x] K[x] ∃ ∃ 唯一的1对多项式 h ( x ) , r ( x ) h(x),r(x) h(x),r(x),使得 f ( x ) = h ( x ) g ( x ) + r ( x )   ( d e f   r ( x ) < d e g   g ( x ) ) ( 3 ) f(x)=h(x)g(x)+r(x)\,(def\,r(x)<deg\,g(x))\qquad(3) f(x)=h(x)g(x)+r(x)(defr(x)<degg(x))(3)其中 f ( x ) f(x) f(x)称为被除式, g ( x ) g(x) g(x)称为除式, h ( x ) h(x) h(x)称为商式, r ( x ) r(x) r(x)称为余式,(3)式称为除法算式
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    该定理表明:数域 K K K上的一元多项式环 K [ x ] K[x] K[x]是具有除法算式的环,除法算式是 K [ x ] K[x] K[x]中有关加法和乘法的第1个重要等式

    (2)整除的判定:

    推论1:设 f ( x ) , g ( x ) ∈ K [ x ] f(x),g(x)∈K[x] f(x),g(x)K[x] g ( x ) ≠ 0 g(x)≠0 g(x)=0,则 g ( x )   ∣   f ( x ) g(x)\,|\,f(x) g(x)f(x)当且仅当 g ( x ) g(x) g(x) f ( x ) f(x) f(x)的余式为0
    在这里插入图片描述

    命题7:设 f ( x ) , g ( x ) ∈ K [ x ] f(x),g(x)∈K[x] f(x),g(x)K[x],数域 F ⊇ K F\supe K FK,则 在 K [ x ] 中 , g ( x )   ∣   f ( x ) ⇔ 在 F ( x ) 中 , g ( x )   ∣   f ( x ) 在K[x]中,g(x)\,|\,f(x)⇔在F(x)中,g(x)\,|\,f(x) K[x],g(x)f(x)F(x),g(x)f(x)
    在这里插入图片描述
    该命题表明:整除性不随数域的扩大而改变(既不会因为数域扩大而变得可以整除,也不会因此而变得不能整除)
    根本原因在于数域对四则运算封闭

    注意:但如果数域缩小,可能变得不能整除,即仅有:
    f ( x ) , g ( x ) ∈ F [ x ] f(x),g(x)∈F[x] f(x),g(x)F[x],数域 F ⊇ K F\supe K FK,则 在 K [ x ] 中 , g ( x )   ∣   f ( x ) ⇒ 在 F ( x ) 中 , g ( x )   ∣   f ( x ) 在K[x]中,g(x)\,|\,f(x)⇒在F(x)中,g(x)\,|\,f(x) K[x],g(x)f(x)F(x),g(x)f(x)而没有"⇐",因为 f ( x ) , g ( x ) , h ( x ) , r ( x ) f(x),g(x),h(x),r(x) f(x),g(x),h(x),r(x)均不一定属于 K [ x ] K[x] K[x]

    (3)综合除法:
    在这里插入图片描述
    在这里插入图片描述
    3.整数环中的带余除法:

    定理3:对 ∀ a , b ∈ Z   ( b ≠ 0 ) ∀a,b∈Z\,(b≠0) a,bZ(b=0), ∃ ∃ 唯一1对 q , r ∈ Z q,r∈Z q,rZ,使得 a = q b + r   ( 0 ≤ r < ∣ b ∣ ) ( 17 ) a=qb+r\,(0≤r<|b|)\qquad(17) a=qb+r(0r<b)(17)
    在这里插入图片描述

    4. λ − λ- λ矩阵的相抵标准型(带余除法的应用之一)
    (1)整环上的矩阵:
    在这里插入图片描述
    (2)相抵:
    在这里插入图片描述
    (3)相抵标准形:
    在这里插入图片描述

    定理4:任意1个非零的 n n n λ − λ- λ矩阵 A ( λ ) A(λ) A(λ)一定相抵于对角 λ − λ- λ矩阵 d i a g { d 1 ( λ ) , d 2 ( λ ) . . . d n ( λ ) } ( 18 ) diag\{d_1(λ),d_2(λ)...d_n(λ)\}\qquad(18) diag{d1(λ),d2(λ)...dn(λ)}(18)其中 d i ( λ )   ∣   d i + 1 ( λ )   ( i = 1 , 2... n − 1 ) d_i(λ)\,|\,d_{i+1}(λ)\,(i=1,2...n-1) di(λ)di+1(λ)(i=1,2...n1),并且对于非零的 d i ( λ ) d_i(λ) di(λ),其首项系数为1.满足这些要求的对角 λ − λ- λ矩阵 ( 18 ) (18) (18)称为 A ( λ ) A(λ) A(λ)的1个相抵标准形Smith标准形
    在这里插入图片描述

    在这里插入图片描述
    定理5:整数环 Z Z Z上任意1个非零的 n n n A A A一定相抵于 Z Z Z上的对角矩阵 d i a g { d 1 , d 2 . . . d n } ( 22 ) diag\{d_1,d_2...d_n\}\qquad(22) diag{d1,d2...dn}(22)其中 d j ∈ N   ( j = 1 , 2... n ) d_j∈N\,(j=1,2...n) djN(j=1,2...n),并且 d i   ∣   d i + 1   ( i = 1 , 2... n − 1 ) d_i\,|\,d_{i+1}\,(i=1,2...n-1) didi+1(i=1,2...n1).满足这些要求的对角矩阵 ( 22 ) (22) (22)称为 A A A的1个相抵标准形Smith标准形
    在这里插入图片描述

    展开全文
  • 多项式除法

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

    千次阅读 2018-04-07 17:52:54
    首先先说一下整除的概念整除:设a , b是两个整数,且b!...接下来就是带余除法的定义及其证明:带余除法:设a , b是两个整数,且b != 0,则存在唯一的整数 q , r (0 &lt;= r &lt; |b|),使得 ...
  • 目录 @0 - 参考资料@ @1 - 前置技能@ @2 - 一些概念@ @3 - 多项式求逆元@ @理论推导@ @参考代码@ @例题与应用@ @4 - 多项式除法与取余@ @理论推导@ ...
  • 用 C语言实现一元多项式的运算(相加,相减,相乘) 1.创建多项式时,无论指数项按什么顺序输入,输出均能实现...2.能够入确切的X计算出最终多项式的值。 模块划分 本程序划分为9个模块,分别是: 1.主函数模块 ...
  • 多项式余除法
  • 综合除法求解特征多项式

    千次阅读 2012-06-05 22:56:05
    X^3-2X^2-X+2,这个是怎么通过综合除法求出矩阵方程的特征值X1=1,X2=-1,X3=2?...将X^3-2X^2-X+2分理出系数,用综合除法 1 -2 -1 2 | 1 +1 -1 -2 |-------------------- 1 -1 -2 0 式是X^2-X-2,而
  • 多项式求逆元

    千次阅读 2017-11-07 17:21:25
    Contents [hide] 1 概述2 基本概念3 多项式的...多项式求逆元是多项式除法多项式取模的必要过程,在竞赛中,有时候多项式求逆元的应用比多项式除法还要多,用快速傅里叶变换以及倍增算法可以做到在 O(nlogn
  • 一.一元多项式的根(7.6) 二.复数域上的不可约多项式(7.6) 三.实数域上的不可约多项式(7.7) 四.实数系多项式的根(7.7)
  • 多项式全家桶
  • 多项式函数 多项式函数是只包含加法和乘法,对一个变量的各次幂进行加法和乘法操作的函数: f(x) = a[n]*x^n + a[n-1]*x^(n-1) + … + a[2]*x^2 + a[1]*x + a[0] numpy中通过将变量x的各次幂(从高到底的顺序)...
  • 【信号与系统】多项式化简方法

    千次阅读 2016-12-26 19:34:00
    多项式除法 简介 多项式除法是代数中的一种算法,用一个同次或低次的多项式去除另一个多项式。是常见算数技巧长除法的一个推广版本。它可以很容易地手算,因为它将一个相对复杂的除法问题分解成更小的一些...
  • 多项式 学习笔记

    2021-01-29 19:02:00
    NTT多项式乘法逆多项式ln泰勒展开牛顿迭代(多项式复合求根)多项式exp多项式开根多项式快速幂 1 这篇博客会讲一下我学多项式的板子(可能不太完善,还请谅解)。 板子参考了 这里。 学习资料: 多项式与生成函数...
  • 多项式各种操作

    2019-07-28 23:12:34
    知识点系列之---多项式(求逆,开方,除法,取模,微积分,Ln,Exp,快速幂,多点求值,快速插值,下降幂乘法)
  • 多项式 单项式:由数字和字母组成的积的代数式称为单项式 多项式:由若干个单项式相加组成的代数式叫做多项式 (废话,这上过初中的人都知道) 一、一元多项式 设\(n\in N^*\),则我们称多项式 \[ a_nx^n+a_{n-1}x^{...
  • 数学基础之数学(4)——多项式 1、基础概念 多项式中有一个未知数就是一元(如xxx),有两个未知数就是二元(如x,yx,yx,y),以此类推。这里主要针对医院多项式展开讨论。给定一个实数域RRR,一个变量(未知数)...
  • 高等代数---多项式

    千次阅读 多人点赞 2020-08-10 19:34:52
    高等代数–多项式 声明: 本篇文章内容主要对《高等代数》第三版第一章内容的总结,复习。 数域 按照所研究的问题,我们常常需要明确规定所考虑的数的范围,在不同的范围内,所得到的结果可能是不同的。 数的概念...
  • 多项式总结&多项式板子 三角/反三角是不可能放的(也不可能真香的 多项式乘法(DFT,FFT,NTT,MTT) 背板子 前置知识:泰勒展开 如果\(f(x)\)在\(x_0\)处存在\(n\)阶导,那么 \[f(x)=\sum_{i=0}^{\infty}\frac{f^...
  • 多项式小结

    2021-07-23 14:06:04
    多项式 文章目录多项式一 简介二 ...多项式求逆六 多项式开方七 多项式除法|取模八 多项式对数函数|指数函数九 牛顿迭代法十 多项式三角函数十二 多项式反三角函数 一 简介 **多项式的度:**对于一个多项式f(x)f(x
  • 在实现多项式运算的代码时,突然觉得抽象急剧增加,感觉我的大脑要到极限了,写的代码完全就是调试出来的,对于代码的结构我自己都感到有点模糊,想表述清楚基本不可能了,凑活着记录一下吧。 现在我对抽象的理解是...
  • 多项式操作

    2019-07-14 17:37:00
    目录 多项式运算从入门到入坟 1. 前言和前置知识 2. 微积分基础知识 2. 1 积分 2. 2 导数 2. 3 不定积分和微积分基本定理 2. 4 基本函数求导公式 2. 5 求导运算法则 2. 6 常...
  • 基本表示及性质: \[i=\sqrt{-1}\] \(i\)是虚数单位 1.坐标(代数)形式: \[z=a+bi\] 当b为0是z为实数,当a为0时为纯虚数 注:复数包括实数和虚数,虚数下有纯虚数 虚数z对应了复平面上的一点(a,b) 运算法则: 设复数...
  • 昨天白天看了看多项式的一些东西,完全看不懂,于是晚上学一学多项式的基本运算。 以下用字母 \(f\) 表示多项式,带下标的字母表示系数 \(f_i\) ,\([n]\) 表示 \(\text{mod}~x^n\) 。 加减法 \[ (f+g)(x)=\sum _{i=...
  • 多项式科技初步

    2019-03-02 11:33:00
    写在前面 为了体现简洁,在每一部分只会放关键代码。 代码具有一定的通用性,保证代码之间函数的调用是合法的。 如果 MathJax 加载不出来或加载有误,请您多刷新几次。...多项式乘法 问题描述 给定两个多项...
  • 多项式全家桶

    2019-03-07 08:04:00
    5.多项式余除法。 6.多项式开根。 7.多项式对数函数。 8.多项式指数函数。 9.多项式的k次幂/k次方根 10.多项式插值 正片开始: 1.多项式加法:(略) 2.多项式减法:(略) 3.多项...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,313
精华内容 525
热门标签
关键字:

多项式的代余除法