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 ll mod = 1e9 + 7;
  7.  
  8. bool notPrime[maxn];
  9. ll ch[maxr + 50][25];
  10. vector<ll> primes;
  11. vector<int> l[maxn];
  12.  
  13. int main() {
  14. 	ios::sync_with_stdio(false);
  15. 	cin.tie(NULL);
  16.  
  17. 	ch[0][0] = 1;
  18. 	for(int i = 1; i <= 1e6 + 22; i++) {
  19. 		ch[i][0] = 1;
  20. 		for(int j = 1; j <= 20; j++) {
  21. 			ch[i][j] = (ch[i - 1][j - 1] + ch[i - 1][j]) % mod;
  22. 		}
  23. 	}
  24.  
  25. 	for(int i = 2; i <= 1e6; i++) {
  26. 		if(!notPrime[i]) {
  27. 			primes.push_back(i);
  28. 			l[i].push_back(1);
  29. 			for(int j = i + i; j <= 1e6; j += i) {
  30. 				notPrime[j] = true;
  31. 				l[j].push_back(1);
  32. 				for(int k = j/i; k % i == 0; k /= i) {
  33. 					l[j].back()++;
  34. 				}
  35. 			}
  36. 		}
  37. 	}
  38.  
  39. 	int q;
  40. 	scanf("%d", &q);
  41. 	while(q--) {
  42. 		int r, n;
  43. 		scanf("%d%d", &r, &n);
  44. 		ll ans = 0;
  45. 		if(r == 0) {
  46. 			printf("%d\n", 1 << l[n].size());
  47. 		}
  48. 		else {
  49. 			vector<int> divs;
  50. 			divs.push_back(1);
  51. 			int N = n;
  52. 			for(int p : primes) {
  53. 				if(n == 1 || p*p > n) {
  54. 					break;
  55. 				}
  56. 				int lst = 0;
  57. 				while(n % p == 0) {
  58. 					int end = divs.size();
  59. 					for(int i = lst; i < end; i++) {
  60. 						divs.push_back(p*divs[i]);
  61. 					}
  62. 					lst = end;
  63. 					n /= p;
  64. 				}
  65. 			}
  66. 			if(n != 1) {
  67. 				int end = divs.size();
  68. 				for(int i = 0; i < end; i++) {
  69. 					divs.push_back(n*divs[i]);
  70. 				}
  71. 			}
  72. 			for(int d : divs) {
  73. 				ll coeff = 1;
  74. 				for(int x : l[d]) {
  75. 					coeff = (coeff * ch[r + x - 1][x]) % mod;
  76. 				}
  77. 				ans = (ans + coeff*(1 << l[N/d].size())) % mod;
  78. 			}
  79. 			printf("%lld\n", ans);
  80. 		}
  81. 	}
  82.  
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0.52s 234752KB
comments (?)
stdin
copy 
5
0 30
1 25
3 65
2 5
4 48
stdout
copy 
8
5
25
4
630
https://ideone.com/KHMSAs
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!