Educational Codeforces-13D: Iterated Linear Function（费马小定理）

数论

Description

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, n$ and $x$ find the value of $g^{(n)}(x)$ modulo $10^9+7$.

Input

The only line contains four integers $A, B, n$ and $x$ $(1 ≤ A, B, x ≤ 10^9, 1 ≤ n ≤ 10^{18})$ — 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 $10^9 + 7$.

Input

3 4 1 1
3 4 2 1
3 4 3 1

Output

7
25
79

题意：$f(x)=Ax+B$，$g^{(0)}(x)=x$ ， $g^{(n)}(x)=f(g^{(n-1)}(x))$，给出A,B,n和x，求$g^{(n)}(x)$ 模 $10^9+7$ 的值。

分析：把$g^{(0)}(x)$，$g^{(1)}(x)$，$g^{(2)}(x)$……写出来之后发现：
$g^{(0)}(x)=x$
$g^{(1)}(x)=Ax+B$
$g^{(2)}(x)=A^2x+AB+B$
$g^{(3)}(x)=A^3x+A^2B+AB+B$
……
得到：
$g^{(n)}(x)$
$=A^nx+A^{n-1}B+A^{n-2}B+……+AB+B$
$=A^nx+B*(A^{n-1}+A^{n-2}+……+A+1)$

因此后面一部分为等比数列，可以用等比数列求和公式求值，公比为 A
$g^{(n)}(x)=A^nx+B*(A^n-1)/(A-1)$
可以看出，A 不能为1，所以要特判A为1时的情况
$A=1$时，$g^{(n)}(x)=x+n*B$

又因为要模$10^9+7$，等比公式求和的时候出现了分数，因此我们用到费马小定理，
$(A-1)^{mod-2}$即为$A-1$关于模mod的乘法逆元，就将除法转化为了乘法。

• 完整代码：

#include<stdio.h>
#define LL long long
const LL MOD=1e9+7;
LL quick(LL x,LL m,LL n)
{
    LL ans=1;
    while(m>0)
    {
        if(m%2==1)
            ans=ans*x%n;
        x=x*x%n;
        m=m/2;
    }
    return ans;
}
int main()
{
    LL a,b,n,x,s,ss,sss;
    LL zuo,you;
    while(scanf("%lld%lld%lld%lld",&a,&b,&n,&x)!=EOF)
    {
        if(a==1)    //特判a为1的时候
            sss=(x%MOD+((b%MOD)*(n%MOD))%MOD)%MOD;
        else
        {
            s=quick(a,n,MOD); //a^n
            zuo=(s*x%MOD)%MOD; //x*a^n; //非等比数列部分
            ss=quick(a-1,MOD-2,MOD); //求a-1关于mod的乘法逆元
            you=(s-1%MOD+MOD)%MOD; //a^n -1 %MOD  分子部分
            you=you*ss%MOD*b%MOD; 
            sss=(zuo+you)%MOD; 
        }
        printf("%lld\n",sss);
    }
    return 0;
}