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[], p2[];

int main() {

    int t;

    scanf("%d", &t);

    int cas = ;

    while (t--) {

        scanf("%lld%lld%lld%lld%lld%lld%lld", &n, &A, &K, &a, &b, &m, &P);

        p1[] = ;

        p1[] = A%P;

        for (int i = ; i <= ; i++) {

            p1[i] = (p1[i-]*p1[])%P;

        }

        p2[] = ;

        p2[] = p1[];

        for (int i = ; i <= ; i++) {

            p2[i] = (p2[i-]*p2[])%P;

        }

        long long fx = K;

        long long ans = ;

        for (int i = ; i < n; i++) {

            ans += p2[fx/]*p1[fx%];

            ans %= P;

            fx = (a*fx+b)%m;

        }

        printf("Case #%d: %lld\n", cas++, ans);

    }

    return ;

}

巴特西

UPC 2219: A^X mod P

最新文章

热门文章