結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}