萧山建设银行招聘网站,南通高端网站建设开发,怎么给网站做二维码,网站章子怎么做一些概念
欧拉函数 ϕ ( n ) \phi(n) ϕ(n)
欧拉函数简介
阶
若 g g g和 n n n互质#xff0c;则令 g x % n 1 g^x\%n1 gx%n1的最小正整数 x x x称为 g g g模 n n n的阶。
原根
对于互质的两个正整数 g g g和 n n n#xff0c;如果 g g g模 n n n的阶为 ϕ ( n ) \phi…一些概念
欧拉函数 ϕ ( n ) \phi(n) ϕ(n)
欧拉函数简介
阶
若 g g g和 n n n互质则令 g x % n 1 g^x\%n1 gx%n1的最小正整数 x x x称为 g g g模 n n n的阶。
原根
对于互质的两个正整数 g g g和 n n n如果 g g g模 n n n的阶为 ϕ ( n ) \phi(n) ϕ(n)则称 g g g为 n n n的原根。
求原根
一般的原根都比较小暴力枚举即可。 NTT
前置知识快速傅里叶变换 F F T FFT FFT
在 F F T FFT FFT中我们选择 n n n次单位复根作为 x x x的值因为他们满足消去引理、折半引理、求和引理所以可以用分治的方法将时间复杂度变为 O ( n log n ) O(n\log n) O(nlogn)。但因为用了复数所以在精度上有误差。而在一些题目要求的是带模的多项式乘法所以 F F T FFT FFT就用不了了。那么我们能不能让 x x x取整数值使得这个值也能满足消去引理、折半引理、求和引理呢
设 ϕ ( m ) r × 2 d \phi(m)r\times 2^d ϕ(m)r×2d令 n 2 d n2^d n2d x n i x ϕ ( m ) × i / n ( m o d m ) x_n^ix^{\phi(m)\times i/n}\pmod m xnixϕ(m)×i/n(modm)其中 i ≤ n i\leq n i≤n
则 x n i x_n^i xni有以下性质
1. 消去引理 x d n d k x n k ( m o d m ) x_{dn}^{dk}x_n^k\pmod m xdndkxnk(modm)
证明 x d n d k x ϕ ( m ) × d k / d n x ϕ ( m ) × k / n x n k ( m o d m ) x_{dn}^{dk}x^{\phi(m)\times dk/dn}x^{\phi(m)\times k/n}x_n^k\pmod m xdndkxϕ(m)×dk/dnxϕ(m)×k/nxnk(modm)
2. 折半引理 ( x n k n / 2 ) 2 x n / 2 k ( m o d m ) (x_n^{kn/2})^2x_{n/2}^k \pmod m (xnkn/2)2xn/2k(modm)
证明 ( x n k n / 2 ) 2 x n 2 k n x n 2 k x n / 2 k ( m o d m ) (x_n^{kn/2})^2x_n^{2kn}x_n^{2k}x_{n/2}^k\pmod m (xnkn/2)2xn2knxn2kxn/2k(modm)
3. 求和引理 ∑ i 0 n − 1 ( x n k ) j 0 ( m o d m ) \sum\limits_{i0}^{n-1}(x_n^k)^j0\pmod m i0∑n−1(xnk)j0(modm)
证明 ∑ i 0 n − 1 ( x n k ) j 1 − ( x n k ) n 1 − x n k 0 1 − x n k 0 \sum\limits_{i0}^{n-1}(x_n^k)^j\dfrac{1-(x_n^k)^n}{1-x_n^k}\dfrac{0}{1-x_n^k}0 i0∑n−1(xnk)j1−xnk1−(xnk)n1−xnk00 那么用 x x x来代替 F F T FFT FFT中的 ω \omega ω其他不变就可以求带模数的多项式乘法了。
模数的限制
若模数 m r × 2 k 1 mr\times 2^k1 mr×2k1其中 r r r为奇数 k k k为整数则多项式乘积的次数不能超过 2 k 2^k 2k。
如果题目没有模数那也可以取一个较大的模数保证答案的每一位都小于这个模数用这个模数来做 N T T NTT NTT也是可以的。
一些模数的原根
模数原根最大长度 998244353 119 × 2 23 1 998244353119\times 2^{23}1 998244353119×2231 3 3 3 2 23 2^{23} 223 469762049 7 × 2 26 1 4697620497\times 2^{26}1 4697620497×2261 3 3 3 2 26 2^{26} 226 2281701377 17 × 2 27 1 228170137717\times 2^{27}1 228170137717×2271 3 3 3 2 27 2^{27} 227
例题
多项式乘法FFT
#includebits/stdc.h
using namespace std;
const long long g3,mod998244353;
long long w,wn,a1[5000005],a2[5000005];
long long mi(long long t,long long v){if(v0) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void ch(long long *a,int l){for(int i1,jl/2,k;il-1;i){if(ij) swap(a[i],a[j]);kl/2;while(jk){j-k;k1;}jk;}
}
void ntt(long long *a,int l,int fl){for(int i2;il;i1){if(fl1) wnmi(g,(mod-1)/i);else wnmi(g,mod-1-(mod-1)/i);for(int j0;jl;ji){w1;for(int kj;kji/2;k,ww*wn%mod){long long ta[k],uw*a[ki/2]%mod;a[k](tu)%mod;a[ki/2](t-umod)%mod;}}}if(fl-1){long long nymi(l,mod-2);for(int i0;il;i) a[i]a[i]*ny%mod;}
}
int main()
{int n1,l1,l2;scanf(%d%d,l1,l2);l1;l2;while(nl1l2) n1;for(int i0;il1;i){scanf(%lld,a1[i]);}for(int i0;il2;i){scanf(%lld,a2[i]);}ch(a1,n);ch(a2,n);ntt(a1,n,1);ntt(a2,n,1);for(int i0;in;i){a1[i]a1[i]*a2[i]%mod;}ch(a1,n);ntt(a1,n,-1);for(int i0;il1l2-1;i) printf(%lld ,a1[i]);return 0;
}
