Educational Codeforces Round 13 D. Iterated Linear Function 逆元+公式+费马小定理_1

谁践踏了优雅 2022-07-11 22:56 128阅读 0赞

D. Iterated Linear Function

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Examples

input

3 4 1 1

output

input

3 4 2 1

output

input

3 4 3 1

output

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    using namespace std;
    #define MM(a,b) memset(a,b,sizeof(a))
    #define SC scanf
    #define PF printf
    #define CT continue
    typedef long long ll;
    typedef unsigned long long ULL;
    const int mod = 1000000007;
    const double eps = 1e-10;
    const int inf = 0x3f3f3f3f;
    const int N=2*1e5+10;
    
    ll quick(ll a,ll n)
    {
        ll res=1;
        while(n){
            if(n&1) res=(res*a)%mod;
            a=(a*a)%mod;
            n>>=1;
        }
        return res;
    }
    
    ll yuan(ll n)
    {
        return quick(n,mod-2);
    }
    
    int main()
    {
        ll a,b,n,x;
        while(~SC("%lld%lld%lld%lld",&a,&b,&n,&x)){
            ll ans=0;
            ans+=quick(a,n)*x%mod;
            ans+=b*(quick(a,n)-1)%mod*yuan(a-1)%mod;
            PF("%lld\n",ans);
        }
        return 0;
    }

逆元求法：利用费马小定理

http://blog.csdn.net/qq\_21057881/article/details/51758437