結果
問題 | No.2718 Best Consonance |
ユーザー |
![]() |
提出日時 | 2024-04-05 23:11:11 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,183 ms / 4,000 ms |
コード長 | 1,372 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 9,624 KB |
最終ジャッジ日時 | 2024-10-02 12:52:10 |
合計ジャッジ時間 | 17,431 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <stdio.h> #include <stdlib.h> #define INF 1000000000000LL int cmp_mul_rev (const void *a, const void *b) { long long *a_ = (long long *)a; long long *b_ = (long long *)b; if (a_[0]*a_[1] < b_[0]*b_[1]) { return 1; } if (a_[0]*a_[1] > b_[0]*b_[1]) { return -1; } return 0; } int main () { int n = 0; long long ab[200000][2] = {}; int res = 0; long long ans = 0LL; long long min[200001] = {}; res = scanf("%d", &n); for (int i = 0; i < n; i++) { res = scanf("%lld", ab[i]); res = scanf("%lld", ab[i]+1); } qsort(ab, n, sizeof(long long)*2, cmp_mul_rev); for (int i = 0; i <= 200000; i++) { min[i] = INF; } for (int i = 0; i < n; i++) { long long mul = ab[i][0]*ab[i][1]; for (long long p = 1LL; p*p <= ab[i][0]; p += 1LL) { if (ab[i][0]%p == 0LL) { if (mul/(min[(int)p]*ab[i][0]) > ans) { ans = mul/(min[(int)p]*ab[i][0]); } if (min[(int)p] > ab[i][0]/p) { min[(int)p] = ab[i][0]/p; } if (p*p != ab[i][0]) { if (mul/(min[(int)(ab[i][0]/p)]*ab[i][0]) > ans) { ans = mul/(min[(int)(ab[i][0]/p)]*ab[i][0]); } if (min[(int)(ab[i][0]/p)] > p) { min[(int)(ab[i][0]/p)] = p; } } } } } printf("%lld\n", ans); return 0; }