A^X mod PTime Limit: 5000ms Memory limit: 65536K有疑问？点这里^_^题目描述
It’s easy for ACMer to calculate A^X mod P. Now given seven integers n, A, K, a, b, m, P, and a function f(x) which defined as following.
f(x) = K, x = 1
f(x) = (a*f(x-1) + b)%m , x > 1
Now, Your task is to calculate
( A^(f(1)) + A^(f(2)) + A^(f(3)) + …… + A^(f(n)) ) modular P.
输入
In the first line there is an integer T (1 < T <= 40), which indicates the number of test cases, and then T test cases follow. A test case contains seven integers n, A, K, a, b, m, P in one line.
1 <= n <= 10^6
0 <= A, K, a, b <= 10^9
1 <= m, P <= 10^9
输出
For each case, the output format is “Case #c: ans”.
c is the case number start from 1.
ans is the answer of this problem.
示例输入
23 2 1 1 1 100 1003 15 123 2 3 1000 107
示例输出
Case #1: 14Case #2: 63
提示
来源
2013年山东省第四届ACM大学生程序设计竞赛
题意：求A^X mod P的和。
PS：妥妥的给跪了，用快速幂肯定不行，超时，然后用了一下快速幂+快速乘法还是超时，一直优化优化也优化好，只好去看了下题解，真心给跪了。
思路：这个用到了分解的方法，，将A^f中的f分解为 i* k + j的形式 。保存在数组中，用的时候直接找就好了。
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <sstream>#include <algorithm>#include <set>#include <queue>#include <stack>#include <map>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const int maxn=33333;LL X[maxn+10],Y[maxn+10];LL n,A,K,a,b,m,P;void Init(){int i;X[0]=1;for(i=1;i<=maxn;i++){X[i]=(X[i-1]*A)%P;}LL tmp=X[maxn];Y[0]=1;for(i=1;i<=maxn;i++){Y[i]=(Y[i-1]*tmp)%P;}}void Solve(int icase){int i;LL fx=K;LL res=0;for(i=1;i<=n;i++){res=(res+(Y[fx/maxn]*X[fx%maxn])%P)%P;fx=(a*fx+b)%m;} printf("Case #%d: %lld\n",icase,res);}int main(){int T,icase;scanf("%d",&T);for(icase=1;icase<=T;icase++){scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&A,&K,&a,&b,&m,&P);Init();Solve(icase);}}
莫找借口失败，只找理由成功。(不为失败找理由，要为成功找方法)
