結果

問題 No.2798 Multiple Chain
ユーザー cho435cho435
提出日時 2024-06-28 23:05:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 1,138 bytes
コンパイル時間 2,712 ms
コンパイル使用メモリ 213,628 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 23:05:30
合計ジャッジ時間 3,932 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for(ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

#define TT template<typename T>
TT using vec = vector<T>;
TT bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; }
TT bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; }

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		std::cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

int main(){
	ll n;
	cin>>n;
	map<ll,ll> mp;
	{
		ll cn=n;
		for(ll i=2;i<=1e6;i++){
			while(cn%i==0){
				mp[i]++;
				cn/=i;
			}
			if(cn==1) break;
		}
		if(cn>1){
			ll d=sqrt(cn);
			for(ll b=d-2;b<=d+2;b++) if(b*b==cn){
				mp[b]+=2;
				break;
			}
		}
	}
	vector<vector<ll>> dp(65,vector<ll>(65,0));
	rep(i,0,65) dp.at(i).at(0)=1;
	rep(i,1,65){
		rep(j,1,65){
			for(ll k=0;k<min(i,j)+1;k++){
				dp.at(i).at(j)+=dp.at(k).at(j-k);
			}
		}
	}
	ll ans=1;
	for(auto[x,y]:mp){
		if(y<2) continue;
		ans*=dp.at(y).at(y);
	}
	cout<<ans<<endl;
}
0