結果

問題 No.811 約数の個数の最大化
ユーザー akakimidoriakakimidori
提出日時 2019-04-12 21:34:57
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 994 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 29,520 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-12 19:04:56
合計ジャッジ時間 1,152 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 13 ms
4,348 KB
testcase_03 AC 0 ms
4,348 KB
testcase_04 AC 1 ms
4,352 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 3 ms
4,352 KB
testcase_08 AC 7 ms
4,348 KB
testcase_09 AC 7 ms
4,352 KB
testcase_10 AC 6 ms
4,348 KB
testcase_11 AC 12 ms
4,348 KB
testcase_12 AC 4 ms
4,352 KB
testcase_13 AC 16 ms
4,348 KB
testcase_14 AC 15 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

i32 gcd (i32 a, i32 b) {
  i32 r = a % b;
  while (r > 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
       
void run (void) {
  i32 n, k;
  scanf ("%" SCNi32 "%" SCNi32, &n, &k);
  i32 *f = (i32 *) calloc (n, sizeof (i32));
  for (i32 i = 1; i < n; ++i) f[i] = i;
  for (i32 i = 2; i * i < n; ++i) {
    if (f[i] != i) continue;
    for (i32 j = i * i; j < n; j += i) {
      f[j] = i;
    }
  }
  i32 max = -1;
  i32 cnt = 0;
  for (i32 i = 2; i < n; ++i) {
    i32 g = gcd (i, n);
    i32 c = 0;
    while (g > 1) {
      c++;
      g /= f[g];
    }
    if (c < k) continue;
    i32 len = 1;
    i32 t = i;
    while (t > 1) {
      i32 p = f[t];
      i32 c = 1;
      while (t % p == 0) {
	t /= p;
	c++;
      }
      len *= c;
    }
    if (cnt < len) {
      max = i;
      cnt = len;
    }
  }
  printf ("%" PRIi32 "\n", max);
}

int main (void) {
  run ();
  return 0;
}
0