<JUNGOL> 제곱수 출력 #1092

문제 : https://www.jungol.co.kr/problem/1092

무엇을 구하는 문제인가?

X의 Y제곱을 20,091,024로 나눈 나머지를 구하는 문제이다.

​

해결 전략

-y를 반으로 나누어 결과값을 곱하면, x의 y제곱을 구할 수 있다.(ex. 2^4 = 2^2 * 2^2)

-y를 계속 반으로 나누어 1이나온다면 x를 return하는 식으로 구현가능

-x, y범위가 크니 long long으로 자료형을 정하였다.

​

알고리즘

1. x, y를 입력받는다.

2. Divide함수를 이용해, y를 분할하여준다.

3. 만약 y가 1이라면, x를 리턴

4. 해당함수의 리턴값을 출력하여준다.

​

※주의 할점

y가 0인경우를 고려해야함

​

<소스코드>

#include <stdio.h>

long long Divide(long long x, long long y)
{
    if (y == 1) return x;
    if(y % 2 == 0) return (Divide(x, y / 2) * Divide(x, y / 2)) % 20091024;
    else return (Divide(x, y / 2) * Divide(x, y / 2 + 1)) % 20091024;
}

int main()
{
    int i;
    long long x, y;
    scanf("%lld %lld", &x, &y);
    if(y == 0) printf("1");
    else printf("%lld", Divide(x, y));
    return 0;
}

 

y = 0일 경우 생각을 안해서 틀렸었다.