結果

問題 No.811 約数の個数の最大化
ユーザー 👑 tatyamtatyam
提出日時 2018-06-21 22:04:19
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,367 bytes
コンパイル時間 2,456 ms
コンパイル使用メモリ 201,296 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 04:39:43
合計ジャッジ時間 3,038 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,376 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 4 ms
4,376 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 3 ms
4,376 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 4 ms
4,380 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 4 ms
4,376 KB
testcase_11 AC 4 ms
4,380 KB
testcase_12 AC 4 ms
4,380 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 4 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
次のファイルから読み込み:  /usr/local/gcc7/include/c++/12.2.0/bits/stl_algobase.h:64,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/bits/specfun.h:45,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/cmath:1935,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/x86_64-pc-linux-gnu/bits/stdc++.h:41,
         次から読み込み:  main.cpp:1:
メンバ関数 ‘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/local/gcc7/include/c++/12.2.0/bits/stl_pair.h:585:16: 警告: ‘mn’ may be used uninitialized [-Wmaybe-uninitialized]
  585 |         second = std::forward<second_type>(__p.second);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: 関数 ‘std::pair<int, int> ans(int, int, int, int)’ 内:
main.cpp:13:17: 備考: ‘mn’ はここで定義されています
   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