Submission #3262532


Source Code Expand

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 fac[maxn];

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

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

	// fac[1] = 1;
	// for (int i = 2; i <= n; ++i)
	// 	fac[i] = fac[i-1] * i % mo;

	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;
		// printf("%d:1 ",i);

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

			// printf("%lld ", c[flag][j]);
		}
		// printf("1\n");
		if (i >= n) {
			res[i-n] = c[flag][n-1];
			// printf("%d:%d\n", i-n, res[i-n]);
		}

		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;
			}
			//printf("i:%d count:%d\n", i, count);
			ans = ans * res[count-1] % mo;
		}

	cout << ans << endl;

	return 0;
}

Submission Info

Submission Time
Task D - Factorization
User suzyz
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1230 Byte
Status
Exec Time 2107 ms
Memory 768 KB

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 400 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 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_small_1 1 ms 256 KB
0_small_2 1 ms 256 KB
0_small_3 1 ms 256 KB
1_large_1 2107 ms 768 KB
1_large_2 2103 ms 768 KB
1_large_3 2103 ms 768 KB
2_large_1 2103 ms 768 KB
2_large_2 2103 ms 768 KB
3_prime_1 2103 ms 768 KB
3_prime_10 2103 ms 768 KB
3_prime_11 2107 ms 768 KB
3_prime_12 2103 ms 768 KB
3_prime_13 2103 ms 768 KB
3_prime_14 2103 ms 768 KB
3_prime_15 2103 ms 768 KB
3_prime_16 2103 ms 768 KB
3_prime_17 2103 ms 768 KB
3_prime_18 2103 ms 768 KB
3_prime_19 2103 ms 768 KB
3_prime_2 2103 ms 768 KB
3_prime_20 2103 ms 768 KB
3_prime_21 2103 ms 768 KB
3_prime_22 2103 ms 768 KB
3_prime_3 2103 ms 768 KB
3_prime_4 2103 ms 768 KB
3_prime_5 2103 ms 768 KB
3_prime_6 2103 ms 768 KB
3_prime_7 2103 ms 768 KB
3_prime_8 2103 ms 768 KB
3_prime_9 2103 ms 768 KB
4_hand_1 2103 ms 768 KB
4_hand_2 1 ms 256 KB
4_hand_3 1 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 2103 ms 768 KB