square869120Contest #2 : D - 2016

ほとんどWikipediaとOEISを探す時間だった。
http://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_d

問題

1～Nの整数のうち、約数の数が最大となる整数とその約数の数を答えよ。

解法

高度合成数という単語を知っていればそれを検索するだけ。
OEISには先頭1000個の高度合成数が載っているので、N以下のうち最大のものを求め、素因数分解すればよい。
http://oeis.org/A002182/b002182.txt

Nは大きいが、高度合成数小さい約数の積でできた整数なので余り苦労せず素因数分解できる。

vector<ll> hoge =
{0,1,2,4,6,12,
24,36,48,60,120,
180,240,360,720,840,
1260,1680,2520,5040,7560,
10080,15120,20160,25200,27720,
45360,50400,55440,83160,110880,
166320,221760,277200,332640,498960,
554400,665280,720720,1081080,1441440,
2162160,2882880,3603600,4324320,6486480,
7207200,8648640,10810800,14414400,17297280,
21621600,32432400,36756720,43243200,61261200,
73513440,110270160,122522400,147026880,183783600,
245044800,294053760,367567200,551350800,698377680,
735134400,1102701600,1396755360,2095133040,2205403200,
2327925600,2793510720,3491888400,4655851200,5587021440,
6983776800,10475665200,13967553600,20951330400,27935107200,
41902660800,48886437600,64250746560,73329656400,80313433200,
97772875200,128501493120,146659312800,160626866400,240940299600,
293318625600,321253732800,481880599200,642507465600,963761198400,
1124388064800,1606268664000,1686582097200,1927522396800,2248776129600,
3212537328000,3373164194400,4497552259200,6746328388800,8995104518400,
9316358251200,13492656777600,18632716502400,26985313555200,27949074753600,
32607253879200,46581791256000,48910880818800,55898149507200,65214507758400,
93163582512000,97821761637600,130429015516800,195643523275200,260858031033600,
288807105787200,391287046550400,577614211574400,782574093100800,866421317361600,
1010824870255200,1444035528936000,1516237305382800,1732842634723200,2021649740510400,
2888071057872000,3032474610765600,4043299481020800,6064949221531200,8086598962041600,
10108248702552000,12129898443062400,18194847664593600,20216497405104000,24259796886124800,
30324746107656000,36389695329187200,48519593772249600,60649492215312000,72779390658374400,
74801040398884800,106858629141264000,112201560598327200,149602080797769600,224403121196654400,
299204161595539200,374005201994424000,448806242393308800,673209363589963200,748010403988848000,
897612484786617600};


map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int Q;
	ll N;
	cin>>Q;
	while(Q--) {
		cin>>N;
		x = lower_bound(ALL(hoge),N+1)-hoge.begin()-1;
		auto M=enumpr(hoge[x]);
		ll ret=1;
		FORR(r,M) ret*=(1+r.second);
		_P("%lld %lld\n",ret,hoge[x]);
		
	}
}

まとめ

以外と10^17オーダーまで掲載されているリストが見つからず苦戦した。