백준 문제 15712번 등비수열 문제풀이 c++

https://www.acmicpc.net/problem/15712

15712번: 등비수열

문제해석

r>1일때 등비 수열의 공식이 a(r^n-1)/(r-1) 인데 r-1이 소수가 아니여서 페르마의 소정리를 사용불가능해서 좀 고민했었다

그래서 다른 방법으로 항의 개수가 짝수인 경우와 항의 개수가 홀수인 경우로 나눠서 생각해보았다.

일단 첫항은 나중에 곱해줘도 상관없으므로 그건 빼고 합했을때 항의개수가 홀수 짝수에 따라

점화식이 비슷하지만 약간 다르게 나오는것을 위 그림에서 확인 할 수있었다.

이걸 계산하기위해 r의 거듭제곱을 구하는 함수와 S()를 구하는 함수 두가지를 작성했다.

r의거듭제곱은 분할정복을이용한 거듭제곱을 사용했고 S()는 재귀적으로 작성하였다.

 

코드

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
ll f(ll r,ll n,ll mod);
ll solve(ll r,ll n,ll mod);
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll a,r,n,mod;
    cin>>a>>r>>n>>mod;
    if(mod==1)
    {
        cout<<0;
    }
    else
    {
        if(r==1)
        {
            cout<<(a%mod*n%mod)%mod;
        }
        else
        {
            cout<<(a%mod*solve(r,n,mod)%mod)%mod;
        }
    }
}
ll f(ll r,ll n,ll mod){
    if(n==1)
    {
        return r%mod;
    }
    ll b=f(r,n/2,mod);
    if(n&1)
    {
        return (r%mod*b%mod*b%mod)%mod;
    }
    else
    {
        return (b%mod*b%mod)%mod;
    }
}
ll solve(ll r,ll n,ll mod){
    if(n==1)
    {
        return 1;
    }
    else
    {
        int x=(1%mod+f(r,n/2,mod)%mod)%mod;
        int y=solve(r,n/2,mod)%mod;
        int z=f(r,2*(n/2),mod)%mod;
        if(n&1) //홀수일때
        {
            return (z%mod+(x%mod*y%mod))%mod;
        }
        else //짝수일때
        {
            return (x%mod*y%mod)%mod;
        }
    }
}