結果

問題 No.14 最小公倍数ソート
ユーザー mudbdbmudbdb
提出日時 2015-07-03 03:52:59
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1,370 ms / 5,000 ms
コード長 3,067 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 27,408 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-22 05:55:05
合計ジャッジ時間 16,795 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 0 ms
4,376 KB
testcase_03 AC 15 ms
4,376 KB
testcase_04 AC 1,370 ms
4,376 KB
testcase_05 AC 480 ms
4,380 KB
testcase_06 AC 553 ms
4,376 KB
testcase_07 AC 719 ms
4,380 KB
testcase_08 AC 933 ms
4,380 KB
testcase_09 AC 1,243 ms
4,380 KB
testcase_10 AC 1,220 ms
4,376 KB
testcase_11 AC 1,284 ms
4,380 KB
testcase_12 AC 1,303 ms
4,380 KB
testcase_13 AC 1,319 ms
4,380 KB
testcase_14 AC 1,277 ms
4,380 KB
testcase_15 AC 1,337 ms
4,380 KB
testcase_16 AC 503 ms
4,376 KB
testcase_17 AC 355 ms
4,380 KB
testcase_18 AC 160 ms
4,384 KB
testcase_19 AC 843 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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