kmjp's blog

競技プログラミング参加記です

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オーダーまで掲載されているリストが見つからず苦戦した。

広告を非表示にする