結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2019-07-13 13:32:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 1,809 bytes |
コンパイル時間 | 1,728 ms |
コンパイル使用メモリ | 174,560 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-21 20:06:56 |
合計ジャッジ時間 | 2,547 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second #define pii pair<int, int> #define eb emplace_back #define all(v) v.begin(), v.end() #define rep(i, n) for (int i = 0; i < n; ++i) #define rep3(i, l, n) for (int i = l; i < n; ++i) #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define out(a) cout << a << endl #define SZ(v) (int)v.size() #define inf (int)(1e9+7) vector<pair<int, int> > prime_factorize(int n) { int tmp = n; vector<pair<int, int> > v; for (int i = 2; i * i <= n; ++i) { int cnt = 0; while (tmp % i == 0) { tmp /= i; cnt++; } if (cnt) v.eb(i, cnt); } if (tmp != 1) v.eb(tmp, 1); return v; } vector<int> all_divisor_catch(int n) { vector<int> res; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { res.push_back(i); if (i != n / i) res.push_back(n / i); } } return res; } vector<int> sieve() { const int MAX_N = 100001 + 1; vector<int> v(MAX_N, 0); v[0] = v[1] = 1; for (int i = 2; i * i <= MAX_N; ++i) { int tmp = 2; while (tmp * i <= MAX_N) { v[tmp++ * i] = 1; } } vector<int> v2; rep(i, SZ(v)) if (v[i] == 0) v2.eb(i); return v2; } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { int n, k; cin >> n >> k; pii ans = pii(-1, 0); rep3(i, 1, n) { //nとk個以上共通の素因数もつか auto a = prime_factorize(gcd(n, i)); int sum = 0; rep(i, SZ(a)) sum += a[i].S; if (sum < k) continue; //iの約数の個数 chmax(ans, pii(SZ(all_divisor_catch(i)), -i)); } out(-ans.S); }