//图可能加载比较慢,请稍等
//ps,绝对不是标题党,这篇比我看过的同余定理快速幂取模文章都详细 #include<bits/stdc++.h> using namespace std; #define ll long long const ll mod = 10000; //poww函数输出(a^b)%mod的值 //不能取名为pow,因为已经有pow这个函数了 /* 算法原理简介: 求一个(a^b)%mod的值(求a的b次方对mod取模的值),经常会遇到b很大的情况 比如说(2^10000)%3,哪怕是用long long类型也装不下 但是好在数论中有同余定理这个东西,接下来会说明部分同余定理的原理和 用"指数对半法"来具体实现同余定理快速幂取模 首先(a*b)%mod==[(a%mod)*(b%mod)]%mod (在下图中解释,请看下图) 然后...这东西还是用纸写好描述,还是看完下图再回来看吧 (如果已经看完下面的图片,那你肯定可以一气呵成的看懂下面的代码 ,然后就学会了,多用几次就好了) */ ll poww(ll a,ll b) { ll ans=1,base=a%mod;//手贱精神,没事mod一次a,那么以后就可以用base代替a while(b)//只要b是>=1的, {//如果b是奇数,先提出一个base乘到ans中 if(b&1) ans=(ans*base)%mod;//b&1是位运算的知识(下图有解释) base=(base*base)%mod;//再把底数位置的base平方再mod b/=2;//举例子7/2=3 , 6/2=2,所以当b为奇数时,把一个base提出去 //然后实际上b已经从7变成6,但是地板除法刚好适应这个这个过程,不用再特殊考虑 } return ans; } /* int pow(int x,int y) { int s=1; for(;y;y>>=1,x=(ll)x*x%P)if(y&1)s=(ll)s*x%P; return s; }///比赛时争分夺秒版快速幂取模 //适用于比赛时间紧急,需要用最短的时间写出来,那下面这种写法就很适合 //一共才几行 */
第三张图一直摆不正,将就着看吧...
