Weights 快速幂取模的应用
/*题意为求3^0+3^1+3^2...+3^(n-1)。可以先根据等比求和公式写出值。(3^n-1)/2，求该数对p的mod。令(3^n-1)/2=k*x+p.最后推出公式。*/#include <stdio.h>#define p 9999997long long quickmod(long long a,long long b,long long m){ long long ans=1; while(b) { if(b&1) { ans=(ans*a)%m; b--; } b/=2; a=a*a%m; } return ans;}int main(){ long long n; while(scanf("%lld",&n)==1) { int m=quickmod(3,n,2*p); if(m==0) m=p; int b=(m-1)%(2*p); printf("%d\n",b/2); } return 0;}