結果

問題 No.811 約数の個数の最大化
コンテスト
ユーザー akakimidori
提出日時 2019-04-12 21:34:57
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 994 bytes
コンパイル時間 538 ms
コンパイル使用メモリ 30,464 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 17:29:32
合計ジャッジ時間 1,107 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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