数论在算法方面的基础应用 |
您所在的位置：网站首页 › a*算法入门 › 数论在算法方面的基础应用 |
|
数论在算法方面的基础应用
数论基础
模运算&算数基本定理模运算常用恒等式&符号 注：除法取模要使用逆元 代码实现12345int a,b,c;a %= c,b %= c;int ans1 = (a + b) % c;int ans2 = ((a - b) % c + c) % c; //三步走：模 加 模int ans3 = ((long long) a * b) % c; //一定要记得开成longlong 算数基本定理任何一个大于$1$的自然数$N$，如果$N$不是质数，那么它一定可以唯一分解成有限个质数，即 补充约数倍数的特征：如果一个数字$x=P_1^{b_1}P_2^{b_2}…P_n^{b_n}$是N的约数，那么一定有$\forall b_i\leq a_1$，同理如果x是N的倍数，那么一定有$\forall b_i\geq a_i$ 素因数求法：模拟短除法 12345678910111213inline prime_factor(int n){ for(int i=2;i*i=phi[m]}templateinline void _read(T &x) { x=0;int f=0;char ch=getchar(); while(ch57){f|=(ch=='-');ch=getchar();} while(ch>=48&&ch |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |