fork(1) download
copy 
  1. //by Vanjape Rajas Mangesh
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int,int>   II;
  8. typedef vector< II >      VII;
  9. typedef vector<int>     VI;
  10. typedef vector< VI > 	VVI;
  11. typedef long long int 	LL;
  12.  
  13. #define PB push_back
  14. #define MP make_pair
  15. #define F first
  16. #define S second
  17. #define SZ(a) (int)(a.size())
  18. #define ALL(a) a.begin(),a.end()
  19. #define SET(a,b) memset(a,b,sizeof(a))
  20.  
  21. #define si(n) scanf("%d",&n)
  22. #define dout(n) printf("%d\n",n)
  23. #define sll(n) scanf("%lld",&n)
  24. #define lldout(n) printf("%lld\n",n)
  25. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  26.  
  27. #define TRACE
  28.  
  29. #ifdef TRACE
  30. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  31. template <typename Arg1>
  32. void __f(const char* name, Arg1&& arg1){
  33. 	cerr << name << " : " << arg1 << std::endl;
  34. }
  35. template <typename Arg1, typename... Args>
  36. void __f(const char* names, Arg1&& arg1, Args&&... args){
  37. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  38. }
  39. #else
  40. #define trace(...)
  41. #endif
  42.  
  43. //FILE *fin = freopen("in","r",stdin);
  44. //FILE *fout = freopen("out","w",stdout);
  45.  
  46.  
  47. const int N=2000005;
  48. const int M=100000000;
  49. const int K=30;
  50. const LL MOD=1000000007;
  51.  
  52. VI prim[N];
  53. int vis[N];
  54. LL fact[K],invfact[K];
  55.  
  56. LL powmod(LL a,LL b)
  57. {
  58. 	if(b==0)
  59. 		return 1;
  60. 	LL ret=powmod(a,b/2);
  61. 	ret=(ret*ret)%MOD;
  62. 	if(b%2==1)
  63. 	{
  64. 		ret=(ret*a)%MOD;
  65. 	}
  66. 	return ret;
  67. }
  68.  
  69. LL ncr(int n,int r)
  70. {
  71. 	LL ret=1;
  72. 	if(n>=(int)MOD)
  73. 		return 0;
  74. 	for(int i=0;i<r;i++)
  75. 	{
  76. 		ret=(ret*1LL*(n-i))%MOD;
  77. 	}
  78. 	ret=(ret*invfact[r])%MOD;
  79. 	return ret;
  80. }
  81.  
  82. void pre()
  83. {
  84. 	for(int i=2;i<N;i++)
  85. 		if(!vis[i])
  86. 			for(int j=i;j<N;j+=i)
  87. 			{
  88. 				vis[j]=1;
  89. 				prim[j].PB(i);
  90. 			}
  91.  
  92. 	fact[0]=1ll;
  93. 	invfact[0]=1;
  94.  
  95. 	for(int i=1;i<K;i++)
  96. 	{
  97. 		fact[i]=(fact[i-1]*1LL*i)%MOD;
  98. 		invfact[i]=powmod(fact[i],MOD-2);
  99. 	}
  100. 	return;
  101. }
  102.  
  103.  
  104. int main()
  105. {
  106. 	fast_io;
  107. 	pre();
  108. 	int t;
  109. 	cin>>t;
  110. 	while(t--)
  111. 	{
  112. 		int n,m,z;
  113. 		cin>>n>>z;
  114. 		m=n;
  115. 		LL ans=1;
  116. 		for(int i=0;i<SZ(prim[n]);i++)
  117. 		{
  118. 			int p=prim[n][i];
  119. 			int ct=0;
  120. 			while(m%p==0)
  121. 			{
  122. 				ct++;
  123. 				m=m/p;
  124. 			}
  125. 			ans=(ans*ncr(ct+z-1,ct))%MOD;
  126. 		}
  127. 		cout<<ans<<"\n";
  128. 	}
  129. 	return 0;
  130. }
Runtime error #stdin #stdout 1.31s 81856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w202fV
language:
C++14 (gcc 8.3)
created:
8 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!