UPC 2219: A^X mod P

题形：另类快速幂

题意：

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.

1 <= n <= 10^6

 

0 <= A, K, a, b <= 10^9

1 <= m, P <= 10^9

 

思路：

 

快速幂，求一个很快，但求多个，并不一定快。这里要求10^6次个，反而就很慢了。

所以，求单个的复杂度要比log(10^9)要小。

这里，有一个很棒的想法：用预处理换复杂度。

如果能算出A0~A10e9这么写所有，那么之后算单个复杂度就是1.很棒~当时预处理复杂度承受不了。

这里有个巧妙的方法：A10e10 = A10e5 * A10e5

所以，算出A0~A10e5,然后另B=A10e5, 算出B0~B10e5,之后算单个，复杂度就是2~棒！预处理复杂度被根号了~

 

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>

long long n, A, K, a, b, m, P;
long long p1[100005], p2[100005];

int main() {
    int t;
    scanf("%d", &t);
    int cas = 1;
    while (t--) {
        scanf("%lld%lld%lld%lld%lld%lld%lld", &n, &A, &K, &a, &b, &m, &P);
        p1[0] = 1;
        p1[1] = A%P;
        for (int i = 2; i <= 100005; i++) {
            p1[i] = (p1[i-1]*p1[1])%P;
        }
        p2[0] = 1;
        p2[1] = p1[100005];
        for (int i = 2; i <= 100005; i++) {
            p2[i] = (p2[i-1]*p2[1])%P;
        }
        long long fx = K;
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += p2[fx/100005]*p1[fx%100005];
            ans %= P;
            fx = (a*fx+b)%m;
        }

        printf("Case #%d: %lld
", cas++, ans);
    }
    return 0;
}