글 읽기 - 싸이클 c++)틀렸습니다

leewwo2o 6년 전 0

예시는 맞고 10퍼에서 틀렸다고 나오네요 어디부분을 고쳐야 할까요? 아니면 반례가 무엇일까요?

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main() {
	int n, p,i=0,nn,cnt=0;
	cin >> n >> p;
	nn = n;
	int arr[100000];
	while (1) {
		arr[i] = n;
		n = (n*nn)%p;
		if (n == 0) {
			cout << 1;
			return 0;
		}
		for (int k = 0; k < i; k++) {
			if (arr[k] == n) {
				cnt++;
				while (1) {
					n = (n*nn) % p;
					if (arr[++k] == n) {
						cnt++;
					}
					else if (arr[++k] != n) {
						cout << cnt;
						return 0;
					}
				}
			}
		}
		i++;
	}
	return 0;
}

seico75 6년 전 0

else if (arr[++k] != n) {

이게 만족하는 순간은 k 가 i+1 일때이어야 할 것 같은데.. arr[i+1] 은 값을 넣지 않았기 떄문에 쓰레기값일 것 같습니다.

그러면 쓰레기 값이 뭐냐에 따라서 값이 나올수도 안나올수도 있을 것 같네요. arr[++k] != n 가 아니라 index 로 종료를 체크하면 어떨까 합니다.

그리고

지금 코드는 한번 나왔던 수가 나오면 그 이후가 정말 사이클이 되는지 확인을 하는데

n <- (n * nn) % p 연산의 특성상 한번 나왔던 수가 나오면 현재값까지 무조건 싸이클입니다.

leewwo2o 6년 전 0

감사합니다 수정해서 맞쳤습니다

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

문제

문제

출처

ICPC

싸이클 c++)틀렸습니다

leewwo2o 6년 전 0

seico75 6년 전 0

leewwo2o 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말