백준/1629/Recursion/곱셈

백준/1629/Recursion/곱셈
재귀를 이용한 풀이가 사용된다.

입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

간단하게 A를 B번만큼 곱해서 C로 나눈 나머지를 하면 될거라 생각하지만

func(int a,int b,int c)
{
	int val = 1;
	while(b--)
    {
    	val*=a;
    }
    reutrn val%c;
}

해당 함수를 넣으면 당연히 안돌아간다.
이유는 int 형을 넘어서 long long도 해당 함수를 통해 나오는 값을 담지 못하기 때문이다.

이를 위해 우선 해당 수학식이 우선 필요하다.

a≡b(mod m)

해당 식이 난해할 수 있다. 나는 일단 난해했다.
뜻은 a는 법 m에 대하여 b와 합동이다.라는 뜻인데 쉽게 풀자면
a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같다라고 정의한다는 뜻이다.

a^n * a^n = a^2n
10^2≡4(mod 12)
10^4≡16(mod 12)

상술한 식을 이용하면 즉 a^k을 구할 수 있다면 a^2k도 구할 수 있다는 뜻이고,
a^2k+1도 구할 수 있다는 뜻이다. a^2k+1은 단순히 a를 곱해주면된다.

해당 식을 이용해 우선 재귀식을 짜보면

long long func(long long a,long long b,long long c)
{
	// 초기식을 구한다.
	if(b==1)return a%2
    // k승에 해당하는 값 상술한 값에서 b를 구한다.
    long long val = func(a,b/2,c);
    // k승에 해당하는 값을 얻었으니 2k을 구해준다.
    val = val * val % 2;
    // 2k가 홀수일 경우 즉, b=5일 경우에는 현재 구해진 val은 4승에 대한 나머지 값이니
    // +1을 해준다.
    if(b%2==0) return val;
    return val * a % 2; 
}

풀이

첫번째 풀이

#include<iostream>
#define ll long long
using namespace std;

ll A, B, C;
ll solution(ll, ll, ll);

ll solution(ll a,ll b,ll c)
{
	if (b == 1)return a % c;
	long long temp = solution(a, b / 2, c);
	temp = temp * temp % c;
	if (b % 2 == 0)return temp;
	return temp * a%c;
}

int main()
{
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> A >> B >> C;

	cout<<solution(A, B, C);
}