JUNGOL...124

Intermediate_Coder/분할정복/제곱수 출력

---

문제                                            

X를 Y번 곱한 값을 찾는 프로그램을 작성하라.

결과가 클 수 있기 때문에 결과 값은 20091024로 나눈 나머지를 출력하라.

 

입력 형식                                     

입력의 첫 번째 줄에는 X와 Y가 입력된다.

X와 Y는 모두 0 이상 231-1 이하의 정수이다.

 

출력 형식                                     

X를 Y번 곱한 값을 20091024로 나눈 나머지를 출력하라.

단, 0를 0번 곱한것은 편의상 1로 정한다.

 

입력 예                                        

2 10

 

출력 예                                        

1024

---

PrintSquare.h

#include <iostream>

class PrintSquare : public Base
{
private:
	long long SquareModuler(long long x, long long pow);
};

 

PrintSquare.cpp

void PrintSquare::Code()
{
	long long x, y;
	std::cin >> x >> y;

	std::cout << SquareModuler(x, y);
}

/// <summary>
/// 주어진 값의 제곱수를 20091024로 나눈 나머지를 반환한다.
/// </summary>
/// <param name="x">곱할 값</param>
/// <param name="pow">곱해지는 횟수</param>
/// <returns>제곱수를 20091024로 나눈 나머지</returns>
long long PrintSquare::SquareModuler(long long x, long long pow)
{
	const static int MODULATION{ 20091024 };

	if (pow == 0)
	{
		return 1;
	}

	long long temp{ SquareModuler(x, pow / 2) % MODULATION };
	if (pow % 2 == 0)
	{
		return (temp * temp) % MODULATION;
	}
	else
	{
		return ((temp * temp) % MODULATION * (x % MODULATION)) % MODULATION;
	}
}

 

---

실행 결과 Success(100)

 

※ 문제를 단순화 한 뒤 생각을 하는 연습을 하자. 이번 문제도 단순화 한 뒤 점화식으로 만든 경우 쉽게 해결이 가능했다.

---

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/분할정복/제곱수 출력-JUNGOL