多项式除法及求模的计算复杂度

2019-04-13 14:19发布

站内文章 / 模拟电子
11402 0 1105
这里写图片描述 这里写图片描述 void polynomial_division(int n, int m, long long *A, long long *B, long long *D, long long *R) { static long long A0[MaxN], B0[MaxN]; int p = 1, t = n - m + 1; while(p < t << 1) p <<= 1; fill(A0, A0 + p, 0); reverse_copy(B, B + m, A0); polynomial_inverse(t, A0, B0); fill(B0 + t, B0 + p, 0); transform(p, B0); reverse_copy(A, A + n, A0); fill(A0 + t, A0 + p, 0); transform(p, A0); for(int i = 0; i != p; ++i) A0[i] = A0[i] * B0[i] % mod_v; inverse_transform(p, A0); reverse(A0, A0 + t); copy(A0, A0 + t, D); for(p = 1; p < n; p <<= 1); fill(A0 + t, A0 + p, 0); transform(p, A0); copy(B, B + m, B0); fill(B0 + m, B0 + p, 0); transform(p, B0); for(int i = 0; i != p; ++i) A0[i] = A0[i] * B0[i] % mod_v; inverse_transform(p, A0); for(int i = 0; i != m; ++i) R[i] = (A[i] - A0[i]) % mod_v; fill(R + m, R + p, 0); }
http://blog.miskcoo.com/2015/05/polynomial-division
应用
多项式的扩展欧几里德算法
多项式的乘法逆元
多项式的多点求值