Submission #3262522


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 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;
}

Submission Info

Submission Time
Task D - Factorization
User suzyz
Language C++14 (GCC 5.4.1)
Score 400
Code Size 959 Byte
Status
Exec Time 129 ms
Memory 1792 KB

Test Cases

Set Name Score / Max Score Test Cases
All 400 / 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 13 ms 1664 KB
1_large_2 129 ms 1024 KB
1_large_3 13 ms 1664 KB
2_large_1 15 ms 1792 KB
2_large_2 14 ms 1792 KB
3_prime_1 14 ms 1792 KB
3_prime_10 14 ms 1792 KB
3_prime_11 14 ms 1792 KB
3_prime_12 13 ms 1792 KB
3_prime_13 13 ms 1792 KB
3_prime_14 13 ms 1792 KB
3_prime_15 13 ms 1792 KB
3_prime_16 14 ms 1792 KB
3_prime_17 14 ms 1792 KB
3_prime_18 14 ms 1792 KB
3_prime_19 13 ms 1792 KB
3_prime_2 14 ms 1792 KB
3_prime_20 13 ms 1792 KB
3_prime_21 13 ms 1792 KB
3_prime_22 13 ms 1792 KB
3_prime_3 14 ms 1792 KB
3_prime_4 14 ms 1792 KB
3_prime_5 14 ms 1792 KB
3_prime_6 14 ms 1792 KB
3_prime_7 14 ms 1792 KB
3_prime_8 13 ms 1792 KB
3_prime_9 13 ms 1792 KB
4_hand_1 14 ms 1792 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 14 ms 1792 KB