Educational Codeforces Round 13 D：Iterated Linear Function（数论）

http://codeforces.com/contest/678/problem/D

D. Iterated Linear Function

Consider a linear function f(x) = Ax + B. Let's define g⁽⁰⁾(x) = x and g⁽ⁿ⁾(x) = f(g^(n - 1)(x)) for n > 0. For the given integer values A, B, nand x find the value of g⁽ⁿ⁾(x) modulo 10⁹ + 7.

Input

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 10⁹, 1 ≤ n ≤ 10¹⁸) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Output

Print the only integer s — the value g⁽ⁿ⁾(x) modulo 10⁹ + 7.

 

input

3 4 1 1

output

7

input

3 4 2 1

output

25

input

3 4 3 1

output

79

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
typedef long long ll;
//逆元 费马小定理
ll pow(ll x,ll y)
{
    ll res=1;
    while(y){
        if(y&1) res=res*x%MOD;
        x=x*x%MOD;
        y>>=1;
    }
    return res;
}

int main()
{
    ll a,b,n,x;
    cin>>a>>b>>n>>x;
    ll res;
    if(a==1){
        res=(x+n%MOD*b)%MOD;
    }
    else{
        res=pow(a,n)*x%MOD;
/*
答案是 pow(A,n) + 一个等比数列
式子可以变成等比数列，然后直接用 Sn = B*a1*(q^n-1)/(q-1) 计算
a1 = 0，q = A
因为每次都要取模，所以要用逆元来算，不能直接除以q-1，而是应该乘以它的乘法逆元
根据费马小定理： 假如MOD是素数，且a与MOD互质，那么a^(MOD-1)=1(mod MOD)
当我们除以 q-1 的时候，我们就是乘以 1/(q-1)
所以 (q-1)^(MOD-1)=1%MOD
两边同乘1/(q-1)得：(q-1)^(MOD-2)=(1-q)%MOD
即是下面的算式
*/
        res+=(pow(a,n)-1)*pow(a-1,MOD-2)%MOD*b;
        res=(res%MOD+MOD)%MOD;
    }
    cout<<res<<endl;
    return 0;
}

2016-06-15