D. Iterated Linear Function
Consider a linear function f(x) = Ax + B. Let's define g(0)(x) = x and g(n)(x) = f(g(n - 1)(x)) for n > 0. For the given integer values A, B, nand x find the value of g(n)(x) modulo 109 + 7.
Input
The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — 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(n)(x) modulo 109 + 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 = ;
typedef long long ll;
//逆元 费马小定理
ll pow(ll x,ll y)
{
ll res=;
while(y){
if(y&) res=res*x%MOD;
x=x*x%MOD;
y>>=;
}
return res;
} int main()
{
ll a,b,n,x;
cin>>a>>b>>n>>x;
ll res;
if(a==){
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)-)*pow(a-,MOD-)%MOD*b;
res=(res%MOD+MOD)%MOD;
}
cout<<res<<endl;
return ;
}
2016-06-15