글 읽기 - 1629-곱셈

ohbg123 6년 전 0

3 4 4로 가정 했을때 3 9 27 81이고 나머지는 3 1 3 1이 됩니다.

이런식으로 나머지가 겹칠 수 밖에 없어서 반복되기 전까지 count 하다가

C % count해서 결과 구했는데... M이 커서 메모리초과인 것 같습니다. 이거 살리는

방법 있을까요?

#include <iostream>
#include <cmath>

using namespace std;
long long N, M, C;

int main(void){
	cin >> N >> M >> C;
	int count = 0;
	long long *result = new long long[M];
	long long temp = N;//고정 N값

	for (int i = 1; i <= M; i++){
		result[i - 1] = ((long long)pow(temp % C, i % C)) % C;
		N *= result[i - 1];
		count++;
		if (result[i - 1] == result[0] && i != 1){ break; }
	}

	count = C % count;
	cout << result[count] << endl;
}

jh05013 6년 전 0

거듭제곱 알고리즘에 대해 알아보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1629-곱셈

ohbg123 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말