結果

問題 No.14 最小公倍数ソート
ユーザー mudbdb
提出日時 2015-07-03 03:52:59
言語 C90
(gcc 12.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,067 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 27,648 KB
最終ジャッジ日時 2025-03-11 18:04:16
合計ジャッジ時間 784 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.c:14:1: error: C++ style comments are not allowed in ISO C90
   14 | // 2^13 = 8192
      | ^
main.c:14:1: note: (this will be reported only once per input file)

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
struct num_info {
  int a;
  int pr_n;
  int *pr;
  int *pow;
  int lcm;
};
int *Pr = 0;
int *Pow = 0;
int Pr_end = 0;
int Factor_max = 14;
// 2^13 = 8192
// 2^14 = 16384
void factor_init(int N)
{
  Pr = (int*)malloc(sizeof(int)*N*Factor_max*2);
  Pow = &(Pr[N*Factor_max]);
  return;
}
void factor(struct num_info *A)
{
  A->pr = &(Pr[Pr_end]);
  A->pow = &(Pow[Pr_end]);
  A->pr_n = 0;

  if (A->a >= 2) {
    int N = A->a;
    int pow;
    for (pow=0; N%2 == 0; pow++) {
      N/=2;
    }
    if (pow != 0) {
      A->pr[A->pr_n] = 2;
      A->pow[A->pr_n] = pow;
      A->pr_n++;
    }
  
    int i;
    for (i=3; i*i<=N; i+=2) {
      for (pow=0; N%i == 0; pow++) {
        N/=i;
      }
      if (pow != 0) {
        A->pr[A->pr_n] = i;
        A->pow[A->pr_n] = pow;
        A->pr_n++;
      }
    }
  
    if (N != 1) {
      A->pr[A->pr_n] = N;
      A->pow[A->pr_n] = 1;
      A->pr_n++;
    }
  } else {
    A->pr[A->pr_n] = 1;
    A->pow[A->pr_n] = 1;
    A->pr_n++;
  }

  Pr_end += A->pr_n;
  return;
}
int *Lcm_pr = 0;
int *Lcm_pow = 0;
void lcm_init(struct num_info *A, int N)
{
  int i;
  Lcm_pr = (int*)malloc(sizeof(int)*Factor_max*2*2);
  Lcm_pow = &(Lcm_pr[Factor_max*2]);
  return;
}
void lcm(struct num_info *A, struct num_info *B)
{
  if (A->a == 1) {
    B->lcm = B->a;
  } else if (B->a == 1) {
    B->lcm = A->a;
  } else {
    int i = 0;
    int j = 0;
    int k = 0;
    while (1) {
      if (A->pr[j] < B->pr[k]) {
        j++;
      } else if (A->pr[j] > B->pr[k]) {
        k++;
      } else {
        if (A->pow[j] >= B->pow[k]) {
          Lcm_pr[i] = B->pr[k];
          Lcm_pow[i] = B->pow[k];
          i++; j++; k++;
        } else {
          Lcm_pr[i] = A->pr[j];
          Lcm_pow[i] = A->pow[j];
          i++; j++; k++;
        }
      }
  
      if (j >= A->pr_n) {
        break;
      }
      if (k >= B->pr_n) {
        break;
      }
    }
    int end = i;
    int gcd = 1;
    for (i=0; i<end; i++) {
      for (j=0; j<Lcm_pow[i]; j++) {
        gcd *= Lcm_pr[i];
      }
    }
    B->lcm = A->a * B->a / gcd;
  }
  return;
}
int search_min(struct num_info *A, int N)
{
  int i;
  int min = ~(1 << 31);
  int min_i;
  for (i=0; i<N; i++) {
    if (A[i].lcm < min) {
      min = A[i].lcm;
      min_i = i;
    } else if (A[i].lcm == min) {
      if (A[i].a < A[min_i].a) {
        min_i = i;
      }
    }
  }
  return min_i;
}
int main()
{
  int N;
  struct num_info *A;
  scanf("%d", &N);
  A = (struct num_info*)malloc(sizeof(struct num_info)*N);
  int i;
  for (i=0; i<N; i++) scanf("%d", &(A[i].a));

  factor_init(N);
  for (i=0; i<N; i++) factor(&(A[i]));

  if (N >= 3) {
    lcm_init(A, N);
    int j, k;
    for (i=0; i<N-2; i++) {
      for (j=i+1; j<N; j++) {
        lcm(&(A[i]), &(A[j]));
      }
      k = search_min(&(A[i+1]), N-(i+1));
      if (k > 0) {
        struct num_info W;
        W = A[i+1];
        A[i+1] = A[(i+1)+k];
        A[(i+1)+k] = W;
      }
    }
  }

  for (i=0; i<N-1; i++) printf("%d ", A[i].a);
  printf("%d\n", A[N-1].a);
  return 0;
}
0