<< ABC046-C AtCoDeerくんと選挙速報 | top | アルゴリズムをまとめたwebサイトを作りたい >>

スポンサーサイト

一定期間更新がないため広告を表示しています

スポンサードリンク | - | | - | - |

ABC052-C Factors of Factorial

ABC052も参加出来ました!

前回と同じくA, B, Cは出来たけどDは出来なかった。

これが今の実力か。

Cは勉強した剰余計算が大いに役に立った!

問題文

整数 N が与えられます。 N! の正の約数の個数を 109+7 で割った余りを求めてください。

 

次のようにすればOK。

例えば6!なら素因数分解すると2が4個、3が2個、5が1個出て来る。これらを使うか使わないかの組み合わせで5×3×2通りの約数がある。

さて、問題は素因数分解したことがないということだ。

ぐぐってみると、効率は悪いが試し割りという方法がシンプルでよさげ。Nも最大1000とさして大きくないし。

#include <iostream>
#include <vector>
const int MOD = 1000000007;

void countPN(int n, std::vector<int> &count)//nを素因数に分解し、countを更新
{
	int m = n;
	for(int i=2 ; i*i<=n ; ++i)
	{
		while(m%i == 0)
		{
			m /= i;
			count[i]++;
		}
		if(m==1) break;
	}
	if(m!=1) count[m]++;

}

int main()
{
	int N; std::cin >> N;
	std::vector<int> count(1024);
	for(auto &x : count) x = 0;
	for(int n=2; n<=N; n++) countPN(n, count);

	long long ans = 1;
	for(int n=2; n<=N; n++)
	{
		if(count[n] != 0)
		{
			ans *= count[n]+1;
			ans %= MOD;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

ほれ、剰余計算もばっちしじゃ!

素因数分解とか約数の列挙とか素数の列挙とか抑えとかないかんかな。

ジャジャガッチ | C/C++ | 23:23 | comments(0) | trackbacks(0) |

スポンサーサイト

スポンサードリンク | - | 23:23 | - | - |
Comment









Trackback
URL:

06
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH