結果

問題 No.811 約数の個数の最大化
コンテスト
ユーザー 👑 tatyam
提出日時 2018-06-21 22:04:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,367 bytes
コンパイル時間 2,359 ms
コンパイル使用メモリ 195,532 KB
最終ジャッジ日時 2025-01-05 14:48:37
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 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:
/usr/include/c++/13/bits/stl_pair.h:744:16: warning: ‘mn’ may be used uninitialized [-Wmaybe-uninitialized]
  744 |         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