글 읽기 - 싸이클로 풀 수는 없을까요?? (개인적인 호기심)

rlaalswo01 6년 전 0

처음에 무식하게 풀었다가 당연히 시간 초과를 받았구요~

질문 게시판을 들여다보면서 거듭제곱알고리즘을 푸는 테크닉이 있다는 것을 알았습니다 (재귀)

하지만 그 이전에 제 나름대로 고민하다가, 종이에 끄적여가며 거듭제곱에 대한 나머지가 반복 순환한다는 (그런 것 같다는...!)

제 나름의 결론을 얻고, 그 가설을 토대로 코드를 짜봤습니다. 그리고 몇 가지 예로 테스트를 해보니 결과가 잘 나오네요.

하지만 백준에 제출했더니, 이번엔 메모리 초과를 얻네요.

당연히 제가 생각하기엔 싸이클이 길어봐야 얼마나 길겠어, 라고 생각한 것과 달리 싸이클이 매우 길거나 없는 테스트 케이스가

있어서 벡터에서 메모리 초과가 난 것인데, 그 반례가 궁금해서 개인적인 탐구심에 글 올려봅니다~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


long long result = 1;
long long a, b, c;

vector <int> v;
int cycle;
int flag = 0;


int main()
{
	cin >> a >> b >> c;

	if (a == 1 || b == 1)
	{
		cout << a%c;
		return 0;
	}    // a나 b가 1이면 바로 정답 출력하고 종료


	result = (a)%c;    // 한번 곱한것에 대한 나머지
	v.push_back(result);

	for (int i = 2; i <= b; i++)    //2번째부터 b번째까지 시도
	{
		result = (result*(a%c)) % c;


		if (v[0] == result)    //싸이클이 발견됐다면 반복문 종료
		{
			flag = 1;
			cycle = v.size();
			break;
		}

		v.push_back(result);    //싸이클이 발견되지 않았다면 저장 후 진행

	}

	if(flag==1)    // 싸이클이 발견됐다면 싸이클을 통해 답을 구함.
		result = v[((b-1) % cycle)];


	cout << result;
}

djm03178 6년 전 1

2147483644 2147483647 2147483647 를 넣었더니 약 5초 후에 런타임 에러가 났습니다.

rlaalswo01 6년 전 0

사이클이 엄청 길거나, 사이클이 뒤에서부터 발생하거나 하는 가능성이 있을 것 같은데 더 연구해봐야겠네요. 감사합니다!

junie 6년 전 0

거듭제곱에 대한 나머지의 사이클의 길이는 c가 소수일 때에는 c-1이 되어서 너무 길기 때문에 그런 것 같아요.

자세한 내용은 구글에 오일러 파이 함수를 검색해 보면 될 것 같아요

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

문제

문제

출처

ICPC

싸이클로 풀 수는 없을까요?? (개인적인 호기심)

rlaalswo01 6년 전 0

djm03178 6년 전 1

rlaalswo01 6년 전 0

junie 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말