Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined), problem: (E) Bash Plays with Functions Solution in C/C++

#include <cstdio>
const int mod = 1000000007;
int a[1000010][21];
int b[1000010];
int main() {
	int q, r, n;
	a[0][0] = 1;
	for (int j = 1; j < 21; j++) {
		a[0][j] = 2;
	}
	for (int i = 1; i < 1000010; i++) {
		a[i][0] = 1;
		for (int j = 1; j < 21; j++) {
			a[i][j] = a[i-1][j] + a[i][j-1];
			if (a[i][j] >= mod) {
				a[i][j] -= mod;
			}
		}
	}
	for (int i = 2; i < 1000010; i++) {
		if (b[i]) continue;
		for (int j = i; j < 1000010; j += i) {
			b[j] = i;
		}
	}
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &r, &n);
		int ans = 1;
		while (n != 1) {
			int k = b[n];
			int c = 0;
			while (n % k == 0) {
				n /= k;
				++c;
			}
			ans = (long long)ans * a[r][c] % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *