結果

問題 No.811 約数の個数の最大化
ユーザー tatyamtatyam
提出日時 2018-06-21 22:04:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,367 bytes
コンパイル時間 1,716 ms
コンパイル使用メモリ 205,392 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 21:25:57
合計ジャッジ時間 2,286 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 3 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 3 ms
6,944 KB
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:64,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/specfun.h:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/cmath:1935,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
                 from main.cpp:1:
In member function 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::__conditional_t<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>) [with _T1 = int; _T2 = int]',
    inlined from 'std::pair<int, int> ans(int, int, int, int)' at main.cpp:18:36:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_pair.h:585:16: warning: 'mn' may be used uninitialized [-Wmaybe-uninitialized]
  585 |         second = std::forward<second_type>(__p.second);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function 'std::pair<int, int> ans(int, int, int, int)':
main.cpp:13:17: note: 'mn' was declared here
   13 |             int mn, mx = 0;
      |                 ^~

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define fcout cout << fixed << setprecision(10)
vector<int> factn;
array<int, 100001> fact;
array<pair<int, int>, 100001> mem;
int n;
pair<int, int> ans(int m, int k, int cnt, int at){
    if(!k){
        if(!mem[cnt].first){
            int mn, mx = 0;
            for(int i = cnt ; i < n ; i += cnt) if(mx < fact[i]){
                mx = fact[i];
                mn = i;
            }
        mem[cnt] = make_pair(mx, mn);
        }
        return mem[cnt];
    }
    if(m == k) return ans(m - 1, k - 1, cnt * factn[at], at + 1);
    auto a = ans(m - 1, k - 1, cnt * factn[at], at + 1);
    auto b = ans(m - 1, k, cnt, at + 1);
    if(a.first == b.first) return a.second < b.second ? a : b;
    return a.first > b.first ? a : b;
}
int main(){
    int k;
    rep(i, 1, 100001){
        for(int j = i ; j < 100001 ; j += i){
            fact[j]++;
        }
    }
    cin >> n >> k;
    int a = n;
    for(int i = 2 ; ; i++){
        while (fact.at(i) - 2) {
            i++;
        }
        if(a % i == 0){
            a /= i;
            factn.push_back(i);
            if(fact[a] == 2){
                factn.push_back(a);
                break;
            }
            i--;
        }
    }
    cout << ans(factn.size(), k, 1, 0).second << endl;
}
0