来到数论王国,一切都得重新开始啦
模运算,顾名思义,对一个数进行取模运算,在大数运算中,模运算是常客
如果一个数太大无法直接输出,或者是不需要直接输出,可以对他进行取模缩小数值在输出
我们习惯这样写:a%b=c
取模的结果一般满足于0<=c<=m-1,m一般是题目给的数据范围
而对于取模操作,满足一下的性质:
(a+b)%c=((a%c)+(b%c))%c;
(a-b)%c=((a%c)-(b%c))%c;
(a*b)%c=((a%c)*(b%c))%c;
而除法就不行了,除法如果进行上面的取模操作是错误的,
那怎么办呢?对于除法取模操作,在同余和逆元中会展开讲解,这里我李某人先讲讲所谓的基本数论操作
那取模运算我们就算讲完了,接下来我们来讲讲所谓的快速幂运算
幂运算我们老生常谈,而快速幂就为了快速解决幂次运算的,当一个数很大的时候进行幂次运算的时候,一般两种情况:要么炸,要么超时
我们可以采取一下两种办法来解决这个问题:
一、
我们可以很容易想到,先算a^2,在a^2^2,一直算到结束,我们可以用递归分治的思想来解决
long long fastpow(long long a,long long b) { if(b==0) return 1; long long temp=(fastpow(a,b/2));//分治递归了 if(b%2==1)//如果是奇数次,还要多乘一个 return (temp*temp*a); else //偶数次正好乘完 return (temp*temp); }
这种方法是较为好想到的;
我们再来介绍另外一种方法--其实也是老生常谈了,只不过换了一个形式--我们在多重背包中所见的二进制优化
将a^11分解成a^8,a^2,a^1的乘积
而a^2=a^1*a^1,a^4=a^2*a^2;
a^8同理,都是二的倍数,产生的a^i都是倍数关系,一步一步递归就可以了
另一方面,我们在分解像n这样的数字的时候,我们也可以采取二进制的思想,我们很清楚 ,对于二进制来说,二进制的前一位数字的值都比低一位的数字的值多2倍;
举个例子来讲;
我们用10进制来表示11;
那对应的2进制就是1011;
就可以表示成2^3+2^1+2^0
还有一个需要考虑的是,对于二进制中的0,我们可以采用二进制中的位运算的方法来跳过:
(1)n&1,如果不是1,就直接跳了就