結果

問題 No.811 約数の個数の最大化
ユーザー ahe100ahe100
提出日時 2019-04-12 23:09:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,027 bytes
コンパイル時間 2,343 ms
コンパイル使用メモリ 208,624 KB
実行使用メモリ 13,764 KB
最終ジャッジ日時 2024-09-15 06:12:32
合計ジャッジ時間 3,417 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
11,848 KB
testcase_01 AC 25 ms
11,648 KB
testcase_02 AC 29 ms
12,720 KB
testcase_03 AC 25 ms
11,776 KB
testcase_04 AC 29 ms
11,904 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 25 ms
11,904 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 29 ms
12,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;

/*
*/

struct D{
	ll val,num,id;
};
bool operator<(const D &l, const D &r){//全順序を定めないと，{1,0,0}=={1,1,0}
	if(l.num > r.num){
		return true;
	}else if(l.num == r.num){
		if(l.val > r.val){
			return true;
		}else if(l.val == r.val){
			return l.id > r.id;
		}
	}
	return false;
}

ll n,k,m;

//2からprob_sizeまでの全ての数の素因数分解（ただし重複無視）を返す
const ll prob_size=100000;//ここの100000は発生する数の範囲
vector<ll> fact[100010],pri;
ll a[100010]={},nu[100010],ans=1;

//nまでの素数表を返す
void prime(ll n, vector<ll>& p){
	ll vis[100010]={};
	reg(i,2,n){
		if(vis[i]==0){
			p.push_back(i);
			reg(j,2,n){
				if(j*i>n)break;
				vis[i*j]=1;
			}
		}
	}
}

void init(){
	cin>>n>>k;
	ll visited[100010]={};
	reg(i,2,prob_size){
		if(visited[i]==0){
			reg(j,1,prob_size){
				if(j*i>prob_size)break;
				visited[i*j]=1;
				fact[i*j].push_back(i);//素因数リスト（重複は含まず）
			}
		}
	}
	prime(n,pri);
	rep(i,pri.size())nu[pri[i]]=i;
	m=n;
	// cerr<<"初期化終了"<<endl;
}

int main(void){
	init();
	//fact[n]からk個選び、その後は好きな数を掛ける
	a[0]=0;//???????????????????
	while(k>0){
		rep(i,fact[n].size()){
			if(m%fact[n][i]==0){
				m/=fact[n][i];
				ans*=fact[n][i];
				a[nu[fact[n][i]]]++;
				// cerr<<a[nu[fact[n][i]]]<<endl;
				k--;
			}
			if(k==0)break;
		}
	}
	//ここから最小の奴にいれていく
	priority_queue<D> Q;
	rep(i,pri.size()){
		Q.push({pri[i],a[i],i});
		// cerr<<pri[i]<<"="<<a[i]<<" ";
	}
	// cerr<<endl;
	//下から埋める
	while(!Q.empty()){
		D p = Q.top();Q.pop();
		if(ans*p.val<n){
			ans*=p.val;
			p.num++;
			Q.push(p);
		}
	}
	cout<<ans<<endl;
	return 0;
}
0