Java教程

数论模运算以及快速幂小解

本文主要是介绍数论模运算以及快速幂小解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

来到数论王国,一切都得重新开始啦

模运算,顾名思义,对一个数进行取模运算,在大数运算中,模运算是常客

如果一个数太大无法直接输出,或者是不需要直接输出,可以对他进行取模缩小数值在输出

我们习惯这样写: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,就直接跳了就

这篇关于数论模运算以及快速幂小解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!