글 읽기 - 다른풀이에 대한 질문

starttoday 6년 전 0

안녕하세요

대회 풀이에 나온 솔루션처럼 큰 소수를 출력 하지 않고,

사이클의 크기들의 최소공배수 + 1를 찍었는데 답이 틀렸다고 나옵니다.

위처럼 풀었을때 반례가 있을까요? 아니면 코딩실수인가요? 궁금합니다

#include<stdio.h>
int a[1000010];
bool v[1000010];
 
int gcd(int a, int b) {
  int t;
  if (a < b) {
    t=a;a=b;b=t;
  }
  while (b>0) {
    t=b;
    b=a%b;
    a=t;
  }
  return a;
}
 
int lcm(int a, int b) {
  return a / gcd(a, b) * b;
}
 
int main() {
  int n, i;
  scanf("%d", &n);
  for (i=0;i<n;i++) {
    scanf("%d", &a[i]);
    a[i]--;
  }
 
  int ans = 1;
 
  for (i=0;i<n;i++) {
    if (v[i]) continue;
    int s = i, cnt = 0;
    while (!v[s]) {
      v[s] = true;
      s = a[i];
      cnt++;
    }
 
    if (cnt == 1) {
      printf("-1\n");
      return 0;
    }
    ans = lcm(ans, cnt);
  }
  printf("%d\n", ans+1);
  return 0;
}

koosaga 6년 전 1

반례 데이터가 있습니다 (제가 넣었습니다).

저대로 하면 답의 크기가 기하급수적으로 커질 것입니다.

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

문제

문제

출처

ICPC

다른풀이에 대한 질문

starttoday 6년 전 0

koosaga 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말