• 多项式乘法逆元 - NTT
2021-03-03 11:14:06

递归求解即可

#include

using namespace std;

#define int long long

namespace NTT {

#define pw(n) (1<

const int N=4000005; // 4 times!

const int mod=998244353,g=3;

int n,m,bit,bitnum,a[N+5],b[N+5],rev[N+5];

void getrev(int l){

for(int i=0;i

rev[i]=(rev[i>>1]>>1)|((i&1)<

}

}

int fastpow(int a,int b){

int ans=1;

for(;b;b>>=1,a=1LL*a*a%mod){

if(b&1)ans=1LL*ans*a%mod;

}

return ans;

}

void NTT(int *s,int op){

for(int i=0;i

for(int i=1;i

int w=fastpow(g,(mod-1)/(i<<1));

for(int p=i<<1,j=0;j

int wk=1;

for(int k=j;k

int x=s[k],y=1LL*s[k+i]*wk%mod;

s[k]=(x+y)%mod;

s[k+i]=(x-y+mod)%mod;

}

}

}

if(op==-1){

reverse(s+1,s+bit);

int inv=fastpow(bit,mod-2);

for(int i=0;i

}

}

void solve(vector A,vector B,vector &C) {

n=A.size()-1;

m=B.size()-1;

for(int i=0;i<=n;i++) a[i]=A[i];

for(int i=0;i<=m;i++) b[i]=B[i];

m+=n;

bitnum=0;

for(bit=1;bit<=m;bit<<=1)bitnum++;

getrev(bitnum);

NTT(a,1);

NTT(b,1);

for(int i=0;i

NTT(a,-1);

C.clear();

for(int i=0;i<=m;i++) C.push_back(a[i]);

for(int i=0;i<=min(m*2,N-1);i++) a[i]=b[i]=0;

}

}

const int N=4000005; // 4 times!

const int mod=998244353,g=3;

struct poly {

vector a;

void cut(int n) {

while(a.size()>n) a.pop_back();

}

poly operator *(int b) {

poly c=*this;

for(int i=0;i

return c;

}

poly operator *(const poly &b) {

poly c;

NTT::solve(a,b.a,c.a);

return c;

}

poly operator +(poly b) {

int len=max(a.size(),b.a.size());

a.resize(len);

b.a.resize(len);

poly c;

for(int i=0;i

return c;

}

poly operator -(poly b) {

int len=max(a.size(),b.a.size());

a.resize(len);

b.a.resize(len);

poly c;

for(int i=0;i

return c;

}

};

void print(poly x) {

for(int i=0;i

cout<

}

int n,a[N];

int qpow(int p,int q) {

int r = 1;

for(; q; p*=p, p%=mod, q>>=1) if(q&1) r*=p, r%=mod;

return r;

}

int inv(int p) {

return qpow(p, mod-2);

}

poly solve(poly A, int n) {

A.cut(n);

poly B;

if(n==1) {

B.a.push_back(inv(A.a[0]));

}

else {

poly Bi = solve(A,(n-1)/2+1);

B = Bi*2 - A*Bi*Bi;

B.cut(n);

}

return B;

}

signed main() {

ios::sync_with_stdio(false);

cin>>n;

for(int i=0;i>a[i];

poly A;

for(int i=0;i

poly B = solve(A,n);

print(B);

}

更多相关内容
• 接收多项式r1,r2(r1>=r2),以及多项式长度nums 返回其每一步的商组成的矩阵Q,以及gcd(r1,r2) Poly_Division(r1,r2,nums)： 接收多项式r1,r2(r1>=r2),以及多项式长度nums 返回商，及其余数 Poly_Multi(a,b,nums)...

# 一、解析

Poly_GCD(r1,r2,nums)：
接收多项式r1,r2(r1>=r2),以及多项式长度nums
返回其每一步的商组成的矩阵Q,以及gcd(r1,r2)

Poly_Division(r1,r2,nums)：
接收多项式r1,r2(r1>=r2),以及多项式长度nums
返回商，及其余数

Poly_Multi(a,b,nums)：
接收多项式a,b,以及多项式长度nums
返回乘积

Poly_Multi_Eye(a,b,nums)：
接收多项式a，仅有一个系数为1的多项式b,以及多项式长度nums
返回乘积

# 二、思路

函数Poly_GCD(r1,r2,nums)返回其商的矩阵Q，以及最大公因式gcd
X初始迭代值为gcd，Y初始迭代值为任意多项式
设X初始迭代值为gcd，Y初始迭代值为0
迭代方程如下：
Next_X=Y
Next_Y=X-Q_i*Y
单击查看迭代方程证明
最终输出X,Y迭代值

# 四、代码

## 1、Main

nums=9;
r1=[0 1 0 0 0 0 0 1 1];
r2=[1 0 0 0 1 1 0 1 1];
%高次在前，低次在后
[Q,gcd]=Poly_GCD(r2,r1,nums);
Size=size(Q);
X=gcd;
Y=zeros(1,nums);
for i=1:Size(1)
temp1=Y;
temp2=xor(X,Poly_Multi(Q(i,:),Y,nums));
X=temp1;
Y=temp2;
end
disp(X);
disp(Y);


## 2、Poly_GCD

function [Q,r2] = Poly_GCD(r1,r2,nums)
Q=[];
[q,r3]=Poly_Division(r1,r2,nums);
Q=[q;Q];
while(~(max(r3)==0))
r1=r2;
r2=r3;
[q,r3]=Poly_Division(r1,r2,nums);
Q=[q;Q];
end
end


## 3、Poly_Division

function [Q,r3] = Poly_Division(r1,r2,nums)
Q=zeros(1,nums);
temp1=find(r1==1);
temp2=find(r2==1);
temp3=temp2(1)-temp1(1);
while(temp3>=0)
q1=zeros(1,nums);
q1(1,nums-temp3)=1;
Q=Q+q1;
Poly_Multi(r2,q1,nums);
r3=xor(r1,Poly_Multi(r2,q1,nums));
if(max(r3)==0)
break;
end
r1=r3;
temp1=find(r1==1);
temp3=temp2(1)-temp1(1);
end
end


## 4、Poly_Multi

function [ret] = Poly_Multi(a,b,nums)
temp1=find(b==1);
Size=size(temp1);
ret=zeros(1,nums);
for i=1:Size(2)
temp2=zeros(1,nums);
temp2(1,temp1(i))=1;
ret=xor(ret,Poly_Multi_Eye(a,temp2,nums));
end
end


## 5、Poly_Multi_Eye

function [ret] = Poly_Multi_Eye(a,b,nums)
temp1=find(b==1);
for i=1:nums-temp1(1)
a(1,1:nums-1)=a(1,2:nums);
a(1,nums)=0;
end
ret=a;
end


展开全文
• 题目： 求解算法， 扩展的欧几里得算法 ...cout多项式(";...cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图

题目：

求解算法，扩展的欧几里得算法

/*
@author tilltheendwjx
@blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/
*/
#include<iostream>
using namespace std;
int indexofmax1(int value)
{
int tmp=1;
int count=0;
for(int i=0;i<sizeof(int)*8;++i)
{
if((value&tmp))
count=i;
tmp=tmp*2;
}
return count;
}
void polynomialtostring(int value)
{
int tmp=1;
int flag=0;
int c=indexofmax1(value);
for(int i=0;i<sizeof(int)*8;++i)
{
if((value&tmp))
{
if(i==0)
{
cout<<"1";
}else if(i==1)
{
cout<<"x";
}else
{
cout<<"x^"<<i;
}
flag=1;
if(i<c)
cout<<"+";
}
tmp=tmp*2;
}
if(flag==0)
cout<<"0";
}
int powofvalue(int value)
{
return 1<<(value);
}
int divide(int m,int b,int &remainvalue)
{
int mindex=indexofmax1(m);
int vindex=indexofmax1(b);
if(mindex<vindex)
{
remainvalue=m;
return 0;
}
int c=mindex-vindex;
int tmp=b;
tmp=tmp<<c;
m=m^tmp;
return powofvalue(c)|divide(m,b,remainvalue);
}
int Tx(int ax,int q,int bx)
{
//cout<<endl;
//cout<<ax<<"\t"<<bx<<"\t";
int tmp=1;
int value=0;
for(int i=0;i<sizeof(int)*8;++i)
{
if((q&tmp))
{
value=value^((bx<<i));
}
tmp=tmp*2;
}
//cout<<ax<<"\t"<<value<<"\t";
//cout<<endl;
return ax^(value);
}
int extent_gcd(int m,int b,int &x,int &y)
{
int a1=1,a2=0,a3=m;
int b1=0,b2=1,b3=b;
int remainvalue=0;
while(1)
{
polynomialtostring(a1);
cout<<"    ";
polynomialtostring(a2);
cout<<"    ";
polynomialtostring(a3);
cout<<"    ";
polynomialtostring(b1);
cout<<"    ";
polynomialtostring(b2);
cout<<"    ";
polynomialtostring(b3);
cout<<"    ";
if(b3==0)
return a3;
if(b3==1)
return b3;
int q=divide(a3,b3,remainvalue);
int t1=Tx(a1,q,b1);
int t2=Tx(a2,q,b2);
int t3=remainvalue;
cout<<t1<<endl;
cout<<t2<<endl;
a1=b1;a2=b2;a3=b3;
b1=t1;b2=t2;b3=t3;
x=b2;y=b3;
polynomialtostring(q);
cout<<endl;
}
}
int main(void)
{
int m=283,b=83,x=0,y=0;
cout<<"中间结果如下:"<<endl;
cout<<"a1   a2    a3    b1    b2    b3    q"<<endl;
int reault=extent_gcd(m,b,x,y);
cout<<endl;
cout<<"多项式(";polynomialtostring(b);cout<<")mod(";polynomialtostring(m);cout<<")的乘法逆元是(";polynomialtostring(x);cout<<")"<<endl;
system("pause");
return 0;
}


运行结果如下图

展开全文
• matlab的M函数文件，附带了函数的使用说明了
• 很好的东西，很实用的东西，你懂的。基于Gf的多项式乘法逆元，在很多时候都能够用到。
• cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图 作者：wjh200821 发表于2012-5-15 22:13:00 原文链接 阅读：2 评论：0 查看评论 转载...

题目：

求解算法，扩展的欧几里得算法

/*
@author tilltheendwjx
@blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/
*/
#include<iostream>
using namespace std;
int indexofmax1(int value)
{
int tmp=1;
int count=0;
for(int i=0;i<sizeof(int)*8;++i)
{
if((value&tmp))
count=i;
tmp=tmp*2;
}
return count;
}
void polynomialtostring(int value)
{
int tmp=1;
int flag=0;
int c=indexofmax1(value);
for(int i=0;i<sizeof(int)*8;++i)
{
if((value&tmp))
{
if(i==0)
{
cout<<"1";
}else if(i==1)
{
cout<<"x";
}else
{
cout<<"x^"<<i;
}
flag=1;
if(i<c)
cout<<"+";
}
tmp=tmp*2;
}
if(flag==0)
cout<<"0";
}
int powofvalue(int value)
{
return 1<<(value);
}
int divide(int m,int b,int &remainvalue)
{
int mindex=indexofmax1(m);
int vindex=indexofmax1(b);
if(mindex<vindex)
{
remainvalue=m;
return 0;
}
int c=mindex-vindex;
int tmp=b;
tmp=tmp<<c;
m=m^tmp;
return powofvalue(c)|divide(m,b,remainvalue);
}
int Tx(int ax,int q,int bx)
{
//cout<<endl;
//cout<<ax<<"\t"<<bx<<"\t";
int tmp=1;
int value=0;
for(int i=0;i<sizeof(int)*8;++i)
{
if((q&tmp))
{
value=value^((bx<<i));
}
tmp=tmp*2;
}
//cout<<ax<<"\t"<<value<<"\t";
//cout<<endl;
return ax^(value);
}
int extent_gcd(int m,int b,int &x,int &y)
{
int a1=1,a2=0,a3=m;
int b1=0,b2=1,b3=b;
int remainvalue=0;
while(1)
{
polynomialtostring(a1);
cout<<"    ";
polynomialtostring(a2);
cout<<"    ";
polynomialtostring(a3);
cout<<"    ";
polynomialtostring(b1);
cout<<"    ";
polynomialtostring(b2);
cout<<"    ";
polynomialtostring(b3);
cout<<"    ";
if(b3==0)
return a3;
if(b3==1)
return b3;
int q=divide(a3,b3,remainvalue);
int t1=Tx(a1,q,b1);
int t2=Tx(a2,q,b2);
int t3=remainvalue;
cout<<t1<<endl;
cout<<t2<<endl;
a1=b1;a2=b2;a3=b3;
b1=t1;b2=t2;b3=t3;
x=b2;y=b3;
polynomialtostring(q);
cout<<endl;
}
}
int main(void)
{
int m=283,b=83,x=0,y=0;
cout<<"中间结果如下:"<<endl;
cout<<"a1   a2    a3    b1    b2    b3    q"<<endl;
int reault=extent_gcd(m,b,x,y);
cout<<endl;
cout<<"多项式(";polynomialtostring(b);cout<<")mod(";polynomialtostring(m);cout<<")的乘法逆元是(";polynomialtostring(x);cout<<")"<<endl;
system("pause");
return 0;
}
`

运行结果如下图

作者：wjh200821 发表于2012-5-15 22:13:00 原文链接
阅读：2 评论：0 查看评论

转载于:https://www.cnblogs.com/tilltheendwjx/archive/2012/05/15/2502332.html

展开全文
• 最近在复习现代密码理论中的AES，AES中的字节变换的核心操作就是求GF(28)GF(2^8)GF(28)上的多项式逆元，这个问题困扰了我一段时间，今天终于得到解决，其实计算方式和数论中求两个数的Bezout算法是一样的，这里感谢...
• 题目： /* @author tilltheendwjx @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ */ #...cout)的乘法逆元是(";polynomialtostring(x);cout)"("pause"); return 0; } 运行结果如下图
• 给定一个多项式 $$F(x)$$ ，请求出一个多项式 $$G(x)$$， 满足 \(F(x) * G(x) \...考虑倍增多项式只有一项时就是乘法逆元假设我们现在得到了$G^{'}(x) \equiv F(x) (mod\ x^{\frac{n}{2}})$我们需要求\[G(x)\equiv...
• 文章目录一、前言二、数学基础1、GF(2⁸)有限域内的多项式2、不可约多项式3、多项式模运算3、乘法逆元三、算法步骤1、扩展欧几里得算法2、多项式除法3、多项式乘法四、代码实现1、多项式除法2、多项式乘法3、...
• 概述 多项式求逆元是一个非常重要的知识点，许多多项式操作都需要用到该算法，包括多项式...快速数论变换（NTT），求一个数$x$在模$p$意义下的乘法逆元多项式的逆元 给定一个多项式$A(x)$，其次数为\$deg_A...
• ## 多项式求逆元

千次阅读 2017-11-07 17:21:25
Contents [hide] 1 概述2 基本概念3 多项式的...多项式逆元多项式除法和多项式取模的必要过程，在竞赛中，有时候多项式逆元的应用比多项式的除法还要多，用快速傅里叶变换以及倍增算法可以做到在 O(nlogn
• 1.关于扩展欧几里得算法的理解 首先要先学会欧几里得算法（辗转相除法）： int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } /* c = a % b; a = b; b = c; if b !... bx1 + (a % b)y1 ...
• Euclid算法 乘法逆元 如果 ax+by=1 那么 a×y%x=1 即 a-1%x=y a×x%y=1 即 a-1%y=x
• 注： 1、模2运算 总结一句话：不管是加法还是减法，相同为0，相异为1； 例题：求57的多项式乘法逆元 转载：https://blog.csdn.net/fat_cai_niao/article/details/90439924
• #在有限域GF(2^n)下求多项式乘法 Python代码实现 一、了解运算规则 二、例题展示 三、直接上代码（代码有详细备注，不做一一解释） def yxydxscf(a,b,c): # 不可约多项式系数模二运算 c = str(c)[1:] # 不够8...
• 简单讲解用辗转相除法计算乘法逆元，用于密码学加密，附C语言实现算法（对正整数运算）
• 目录乘法逆元小结逆元的定义求解逆元的方法1. 快速幂测试代码2. 乘法逆元小结 乘法逆元，一般用于求（a / b）(modp)的值（p 通常为质数），是解决模意义下分数数值的必要手段。 关于求余，有以下三种规则： 加法：...
• 复习之路：关于逆元，我们首先知道一个叫做“完全剩余系”的东西，记为Zn,即mod n剩下的数；还有一个叫做 “缩系”的东西...我们要求乘法逆元有两种方式，首先介绍三个定理：1、之前讲到的乘法逆元，即ax = 1 (mod ...
• 逆元——乘法逆元的应用 1、问题引入： （1）对于m=(a/b)(mod p)问题，由于除法不能用同余定理，我们需要将除法转换成乘法 ( a / b ) % p =a * inv ( b , p ) %p =( a%p * inv ( b , p )%p ) %p （其中，inv ( b , p...
• 有限域 GF(28282^8）上的元素满足加法交换群、线性空间，所以，是和整数有限域上的运算等价的，所以可以直接重载扩展欧几里得来计算多项式逆元 /* &amp;gt; Problem:main &amp;gt; Author: ...
• C语言实现GF(2^8)下多项式乘法
• 多项式简介 对于数域F\mathbb FF，若有∀i∈{1,2,3,⋯&ThinSpace;,n}\forall i\in\{1,2,3,\cdots,n \}∀i∈{1,2,3,⋯,n}，则 f(x)=a0+a1x+a2x2+⋯+anx=∑i=1naixif(x)=a_0+a_1x+a_2x^2+\cdots+a_nx=\sum_{i=1}^...
• 整理的算法模板合集： ACM模板 目录多项式求逆一、分治FFT二、倍增法及其...P4238 【模板】多项式乘法逆 直接按照上述的思路实现一下模板即可。注意要中间 h(x)h(x)h(x) 要取的是模 x⌈n⌉2x^{\frac{\lceil n \rceil}

...