fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const int maxr = 1e6 + 6, maxn = 1e6 + 6;
  6. const int mod = 1e9 + 7;
  7.  
  8. bool notPrime[maxn];
  9. int ch[maxr + 50][25];
  10. vector<int> primes;
  11. vector<int> l;
  12.  
  13. int sum(int r, int a, int b) {
  14. 	return (ch[r + b][b] - (a == 0 ? 0 : ch[r + a - 1][a - 1]) + mod);
  15. }
  16.  
  17. int r, n;
  18. int comp(int i, ll coeff, int dist) {
  19. 	if(i == l.size()) {
  20. 		return (coeff*(1 << dist)) % mod;
  21. 	}
  22. 	else {
  23. 		return (comp(i + 1, (coeff*sum(r - 1, 0, l[i] - 1)) % mod, dist + 1)
  24. 				+ comp(i + 1, (coeff*sum(r - 1, l[i], l[i])) % mod, dist)) % mod;
  25. 	}
  26. }
  27.  
  28. int main() {
  29. 	ch[0][0] = 1;
  30. 	for(int i = 1; i <= 1e6 + 22; i++) {
  31. 		ch[i][0] = 1;
  32. 		for(int j = 1; j <= 20; j++) {
  33. 			ch[i][j] = (ch[i - 1][j - 1] + ch[i - 1][j]) % mod;
  34. 		}
  35. 	}
  36. 	for(int i = 1; i <= 1e6 + 22; i++) {
  37. 		for(int j = 1; j <= 20; j++) {
  38. 			ch[i][j] = (ch[i][j] + ch[i - 1][j - 1]) % mod;
  39. 		}
  40. 	}
  41.  
  42. 	for(int i = 2; i <= 1e3; i++) {
  43. 		if(!notPrime[i]) {
  44. 			primes.push_back(i);
  45. 			for(int j = i + i; j <= 1e3; j += i) {
  46. 				notPrime[j] = true;
  47. 			}
  48. 		}
  49. 	}
  50.  
  51. 	int q;
  52. 	scanf("%d", &q);
  53. 	while(q--) {
  54. 		l.clear();
  55. 		scanf("%d%d", &r, &n);
  56. 		for(int p : primes) {
  57. 			if(n == 1 || p*p > n) {
  58. 				break;
  59. 			}
  60. 			else if(n % p == 0) {
  61. 				l.push_back(1);
  62. 				n /= p;
  63. 				while(n % p == 0) {
  64. 					l.back()++;
  65. 					n /= p;
  66. 				}
  67. 			}
  68. 		}
  69. 		if(n != 1) {
  70. 			l.push_back(1);
  71. 		}
  72.         printf("%d\n", (r == 0 ? (1 << l.size()) : comp(0, 1, 0)));
  73. 	}
  74. 	return 0;
  75. }
Success #stdin #stdout 0.06s 102144KB
comments (?)
stdin
copy 
5
0 30
1 25
3 65
2 5
4 48
stdout
copy 
8
5
25
4
630
https://ideone.com/7TEWih
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!