快速幂+乘法逆元求等比数列的和并取模

2019-04-14 20:59发布

站内文章 / 模拟电子
13389 0 1341
等比数列是一种常用的数列 朴素的求和方法是直接每项相加，不会影响取模，代码也很简单，但是时间复杂度为o（n），难以令人满意 于是我们想到了通项公式 我们知道，等比数列和前n项和公式为（a1-a1*q^n）/(1-q). 而通过二分计算快速幂可以在log（n）的时间计算出q^n的值，（代码如下）。剩下的貌似就是简单的除法了 int pow2( int a, int b ) { int r = 1, base = a; while( b != 0 ) { if( b % 2 ) r = (r*base)%mod; base =( base*base)%mod; b /= 2; } return r; }
不过事情没这么简单。 由于等比数列增加很快，很多题目中我们需要对它进行取模，而通项公式中有除法，不能直接取模，于是我们需要使用数论中讲到的模逆元素  在数论中，若 (a/x) %p= ( a *y%p) 我们称y为x模p的逆元素 逆元素存在条件为gcd(x,p)=1; 有结论为，若y为x模p的逆元素，则x*y%p=1. 即x*y与1关于p同余 因此我们可以使用exgcd求得x模p的逆元素exgcd(x,p,&y,&z); 得到一个y，若y为负，调整为正数
求得了x的逆元素，我们就可以通过 (a1*pow(q,n)-1)*y%mod 得到等比数列（a1，q）的前n项和了。 应用：hdu1452 -----求 2004^x(mod 29) 参考资料 http://blog.csdn.net/luyuncheng/article/details/8017016 ac代码： #include #include using namespace std; #define MAX 200000000 #define ull unsigned long long const int MAXN = 100011; int pow2( int a, int b ) { int r = 1, base = a; while( b != 0 ) { if( b % 2 ) r = (r*base)%29; base =( base*base)%29; b /= 2; } return r; } int main() { int x; while(scanf("%d",&x)&&x) { int a=pow2(2,2*x+1); int b=pow2(3,x+1); int c=pow2(22,x+1); printf("%d ",( a - 1 ) * (( b - 1 ) * 15) * ( c - 1 ) * 18 % 29); } return 0; }


热门文章