提出 #3262522


ソースコード 拡げる

Copy
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <cmath>

using namespace std;
const int maxn = 100002;
const int mo = 1000000007;

int n, m;

long long c[2][maxn];
long long res[100];

int main()
{
	cin >> n >> m;
	if (n == 1 || m == 1) {
		cout << 1 << endl;
		return 0;
	}

	int flag = 1;
	c[0][0] = c[0][1] = 1;
	for (int i = 2; i <= n+33; ++i){
		c[flag][0] = c[flag][i] = 1;

		for (int j = 1; j < i && j < 31; ++j) {
			c[flag][j] = c[1-flag][j-1] + c[1-flag][j];
			if (c[flag][j] >= mo)
				c[flag][j] -= mo;
		}
		
		if (i >= n)
			res[i-n+1] = c[flag][i-n+1];

		flag = 1-flag;
	}

	int tmp = m;

	long long ans = 1;
	for (int i = 2; i < m && tmp > 1; ++i)
		if (tmp%i == 0) {
			int count = 0;
			while (tmp%i == 0) {
				tmp /= i;
				++count;
			}

			ans = ans * res[count] % mo;
		}

	cout << ans << endl;

	return 0;
}

提出情報

提出日時
問題 D - Factorization
ユーザ suzyz
言語 C++14 (GCC 5.4.1)
得点 400
コード長 959 Byte
結果 AC
実行時間 129 ms
メモリ 1792 KB

ジャッジ結果

セット名 All Sample
得点 / 配点 400 / 400 0 / 0
結果
AC × 36
AC × 3
セット名 テストケース
All 0_small_1, 0_small_2, 0_small_3, 1_large_1, 1_large_2, 1_large_3, 2_large_1, 2_large_2, 3_prime_1, 3_prime_10, 3_prime_11, 3_prime_12, 3_prime_13, 3_prime_14, 3_prime_15, 3_prime_16, 3_prime_17, 3_prime_18, 3_prime_19, 3_prime_2, 3_prime_20, 3_prime_21, 3_prime_22, 3_prime_3, 3_prime_4, 3_prime_5, 3_prime_6, 3_prime_7, 3_prime_8, 3_prime_9, 4_hand_1, 4_hand_2, 4_hand_3, sample_01, sample_02, sample_03
Sample sample_01, sample_02, sample_03
ケース名 結果 実行時間 メモリ
0_small_1 AC 1 ms 256 KB
0_small_2 AC 1 ms 256 KB
0_small_3 AC 1 ms 256 KB
1_large_1 AC 13 ms 1664 KB
1_large_2 AC 129 ms 1024 KB
1_large_3 AC 13 ms 1664 KB
2_large_1 AC 15 ms 1792 KB
2_large_2 AC 14 ms 1792 KB
3_prime_1 AC 14 ms 1792 KB
3_prime_10 AC 14 ms 1792 KB
3_prime_11 AC 14 ms 1792 KB
3_prime_12 AC 13 ms 1792 KB
3_prime_13 AC 13 ms 1792 KB
3_prime_14 AC 13 ms 1792 KB
3_prime_15 AC 13 ms 1792 KB
3_prime_16 AC 14 ms 1792 KB
3_prime_17 AC 14 ms 1792 KB
3_prime_18 AC 14 ms 1792 KB
3_prime_19 AC 13 ms 1792 KB
3_prime_2 AC 14 ms 1792 KB
3_prime_20 AC 13 ms 1792 KB
3_prime_21 AC 13 ms 1792 KB
3_prime_22 AC 13 ms 1792 KB
3_prime_3 AC 14 ms 1792 KB
3_prime_4 AC 14 ms 1792 KB
3_prime_5 AC 14 ms 1792 KB
3_prime_6 AC 14 ms 1792 KB
3_prime_7 AC 14 ms 1792 KB
3_prime_8 AC 13 ms 1792 KB
3_prime_9 AC 13 ms 1792 KB
4_hand_1 AC 14 ms 1792 KB
4_hand_2 AC 1 ms 256 KB
4_hand_3 AC 1 ms 256 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 14 ms 1792 KB