[原创]第四届山东省赛 A^X mod P [预处理]【思维】

2017-03-12 00:03:17 Tabris_ 阅读数：190

博客爬取于2020-06-14 22:41:19
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61466246

题目链接：http://acm.upc.edu.cn/problem.PHP?id=2219
————————————————————————————————————
2219: A^X mod P
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 142 Solved: 28
[Submit][Status][Web Board]
Description
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.
Input
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
Output
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.
Sample Input
2
3 2 1 1 1 100 100
3 15 123 2 3 1000 107
Sample Output
Case #1: 14
Case #2: 63

————————————————————————————————————

题目大意：
就是给你7个数:
$ n, A, K, a, b, m, P一个公式:一个公式:f(x) = \left{\begin{array}{rcl}\ K &&, x = 1 \ (a*f(x-1) + b)%m && ,x>1\end{array}\right.$

问：
$( A^{f(1)} + A^{f(2)} + A^{f(3)}+ … + A^{f(n)} ) \mod P. $

解题思路:
其实思路很好构建 ,
只要求出f(i)f(i)然后O(nlog⁡n)O(n\log {n})的快速幂就能求解

但是这题卡了log⁡\log ,所以不能快速幂

对于求一次幂 用快速幂会非常快 但是求多次就不是很快了

我们要先预处理出所有{Ax∣x∈[1,P]}\{A^{x}| x\in \big[1,P\big] \}

发现根本存不下 ，P≤109P\leq 10^9，
但是我们可以预处理出
{Ax∣x∈[1,P]}\{A^{x}| x\in \big[1,\sqrt {P}\big] \}
和
{(AP)x∣x∈[1,P]}\{ (A^{\sqrt{P} })^{x}| x\in \big[1,\sqrt {P}\big] \}
这样我们就可以通过一次相乘,开快速求出Z∈{Ax∣x∈[1,P]}Z\in\{A^{x}| x\in \big[1,P\big] \}了

这样下来复杂度就变成了O(Tn)O(Tn)

附本题代码

——————————————————————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# include<bits/stdc++.h>

using namespace std;
typedef long long int LL;
/********************************/

LL Ai[100005];
LL A1e5i[100005];

int main(){
    int _ = 1,kcase = 0;
    scanf("%d",&_);
    while(_--){
        int n, A, K, a, b, m, P;
        scanf("%d%d%d%d%d%d%d",&n, &A, &K, &a, &b, &m, &P);
        Ai[0]=1;
        Ai[1]=A;
        for(int i=1;i<=100000;i++){
            Ai[i]=Ai[i-1]*A%P;
        }
        A1e5i[0]=1;
        A1e5i[1]=Ai[100000];
        for(int i=2;i<=100000;i++){
            A1e5i[i]=A1e5i[1]*A1e5i[i-1]%P;
        }
        LL ans =0,tmp=K;
        for(int i=1;i<=n;i++){
            ans+=Ai[tmp%100000]*A1e5i[tmp/100000];
            (ans>P)?ans%=P:true;
            tmp=tmp*a+b,tmp%=m;
        }

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

    }
    return 0;
}