結果
問題 |
No.811 約数の個数の最大化
|
ユーザー |
![]() |
提出日時 | 2019-08-20 15:55:40 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,214 bytes |
コンパイル時間 | 1,235 ms |
コンパイル使用メモリ | 158,188 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 12:27:26 |
合計ジャッジ時間 | 2,032 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)x.size()) template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;} typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vi> vvi; const int inf = 1LL<<60; const int mod = 1e9 + 7; const double eps = 1e-9; /*{ }*/ int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } signed main(){ int n, k; cin >> n >> k; int ans = 0, div = 0; rep(i, 1, n){ int g = gcd(n, i); int tmp = 0; rep(j, 2, g/j+1){ int c = 0; while(g%j == 0){ c++; g /= j; } tmp += c; } if(g != 1) tmp++; // cout << i << " " << tmp << endl; if(tmp < k) continue; tmp = 1; int t = i; rep(j, 2, t/j+1){ int c = 0; while(t%j == 0){ c++; t /= j; } tmp *= (c+1); } if(t != 1) tmp *= 2; if(chmax(div, tmp)){ ans = i; } // cout << i << " " << tmp << " " << ans << endl; } cout << ans << endl; return 0; }