結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
|
提出日時 | 2019-04-15 22:43:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,600 bytes |
コンパイル時間 | 1,081 ms |
コンパイル使用メモリ | 118,248 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 08:07:27 |
合計ジャッジ時間 | 1,806 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <array>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>#include <memory>#include <regex>using namespace std;int gcd(int a, int b){while(b != 0){int tmp = a % b;a = b;b = tmp;}return a;}void integerFactorization(int n, vector<pair<int, int> >& factor){factor.clear();int a = 2;while(a * a <= n){int b = 0;while(n % a == 0){++ b;n /= a;}if(b > 0)factor.push_back(make_pair(a, b));++ a;}if(n > 1)factor.push_back(make_pair(n, 1));}int solve(int x, int n, int k){int y = gcd(x, n);vector<pair<int, int> > f;integerFactorization(y, f);for(const auto& p : f)k -= p.second;if(k > 0)return -1;integerFactorization(x, f);int ans = 1;for(const auto& p : f)ans *= p.second + 1;return ans;}int main(){int n, k;cin >> n >> k;int maxCnt = -1;int ans = -1;for(int x=1; x<n; ++x){int cnt = solve(x, n, k);if(maxCnt < cnt){maxCnt = cnt;ans = x;}}cout << ans << endl;return 0;}