codeforces_678D. Iterated Linear Function(Quick 멱)

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

빠른 멱구는 등비수열의 합을 구하면 되지만, 모형을 취하려면 제법은 역원을 사용해야 한다는 것을 주의해야 한다.
a^(mod) % mod = a
a^(mod-1) % mod = 1
a^(mod-2) * a %mod = 1

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Si(a) scanf("%d",&a)
#define Sl(a) scanf("%lld",&a)
#define Sd(a) scanf("%lf",&a)
#define Ss(a) scanf("%s",a)
#define Pi(a) printf("%d
",(a))
#define Pl(a) printf("%lld
",(a))
#define Pd(a) printf("%lf
",(a))
#define Ps(a) printf("%s
",(a))
#define W(a) while(a--)
#define mem(a,b) memset(a,(b),sizeof(a))
#define FOP freopen("data.txt","r",stdin)
#define inf 0x3f3f3f3f
#define maxn 1000010
#define mod 1000000007
#define PI acos(-1.0)
#define LL long long
using namespace std;

LL fastpow(LL x,LL n)
{
    LL ans=1;
    while(n)
    {
        if(n&1)ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;

}

int main()
{
    LL a,b,x,ans;
    LL n;
    scanf("%lld%lld%lld%lld",&a,&b,&n,&x);
    if(a==1)
    {
        ans=((n%mod*b)%mod+x)%mod;
    }
    else
    {
        LL an=fastpow(a,n);
        ans=(an-1+mod)%mod;
        ans=ans*fastpow(a-1,mod-2)%mod*b%mod;
        ans=(ans%mod+an*x%mod)%mod;
    }
    Pl(ans%mod);
    return 0;
}

codeforces_678D. Iterated Linear Function(Quick 멱)

좋은 웹페이지 즐겨찾기