sdutoj 2605 A^X mod P

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2605

A^X mod P

Time 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.

示例输入

2
3 2 1 1 1 100 100
3 15 123 2 3 1000 107

示例输出

Case #1: 14
Case #2: 63

提示

来源

2013年山东省第四届ACM大学生程序设计竞赛

分析:

中等难度数论题。

先考虑 X = f(x)

可加可不加的欧拉定理优化 { 注意本题A，P并不一定互质，使用欧拉定理优化的时候注意细节。 A^(X + phi(P)) mod P = A^X mod P 在X>0时成立，注意X=0时和X为phi(P)的倍数时的特判 } 对于取模后的X，在P为质数时，数量级仍达到10^9，考虑到数据量n<=10^6且T=40，显然本题不可用O(logX)的快速幂求解，(希望确实做到了这点，如果有快速幂过的，如果能交流下优化的方法，感激不尽)。

考虑O(1)做法。加欧拉定理优化可令ph = phi(P)，也可以ph取10^9 + 1 我们可以找到一个最小的数 k 满足k*k>ph.

然后对于每一个X，令 X = i*k + j 其中i和j满足 0 <= i < k 且 0 <= j < k

则A^X = A^(i*k +j) = ( (A^k) ^ i ) * (A ^ j)。 A^k为定值，而i，j均<k，两部分%P的值都可以在O(k)时间内预处理出来然后对于每个X进行O(1)求解。

接着考虑f(x)，直接按照题意递推计算即可，需要注意的是x=1时，K没有对m取模，换言之，可能大于m

每组的复杂度为O(sqrt(P) + n)

官方代码：

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long ll;
 9 int n;
10 ll A,K,a,b,m,P;
11 ll powmod(ll a,ll n,ll m){
12     ll y=1;
13     while(n){ 
14         if(n&1) y=y*a%m;
15         n>>=1;
16         a=a*a%m;
17     } 
18     return y;
19 }
20 ll solve(){
21     ll f=K,sum=0,tmp;
22     for(int i=0;i<n;i++){
23         sum=(sum + powmod(A,f,P))%P;
24         f=(a*f + b)%m;
25     }
26     return sum;
27 }
28 int main()
29 {
30 #ifndef ONLINE_JUDGE
31     freopen("data.in","r",stdin);freopen("out.txt","w",stdout);
32 #endif
33     int T,C=0;
34     scanf("%d",&T);
35     while(T--)
36     {
37         scanf("%d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&A,&K,&a,&b,&m,&P);
38         printf("Case #%d: %I64d
",++C,solve());
39     }
40     return 0;
41 }

View Code