fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long dp[2222][2222];
  5.  
  6. vector <int> primes;
  7.  
  8. void f(int n)
  9. {
  10. 	vector <bool> b(n+1,true);
  11. 	b[0]=b[1]=false;
  12. 	for(int i=0;i<b.size();i++)
  13. 	{
  14. 		if(b[i])
  15. 		{
  16. 			for(int j=i*i;j<b.size();j+=i)
  17. 				b[j]=false;
  18. 		}
  19. 	}
  20. 	for(int i=0;i<b.size();i++)
  21. 		if(b[i])
  22. 			primes.push_back(i);
  23. }
  24.  
  25. vector < pair< map <int,int>,vector <int> > > v(2001);
  26. vector <vector <int> > w(2001);
  27.  
  28. void numb(int k,int y)
  29. {
  30. 	if(y==v[k].second.size()-1)
  31. 	{
  32. 		int z=v[k].first[v[k].second[y]];
  33. 		int x=w[k].size();
  34. 		int q;
  35. 		for(int i=1;i<=z;i++)
  36. 		{
  37. 			q=pow(v[k].second[y],i);
  38. 			for(int j=0;j<x;j++)
  39. 			{
  40. 				w[k].push_back(q*w[k][j]);
  41. 			}
  42. 		}
  43. 	}
  44. 	else
  45. 	{
  46. 		int z=v[k].first[v[k].second[y]];
  47. 		int x=w[k].size();
  48. 		int q;
  49. 		for(int i=1;i<=z;i++)
  50. 		{
  51. 			q=pow(v[k].second[y],i);
  52. 			for(int j=0;j<x;j++)
  53. 			{
  54. 				w[k].push_back(q*w[k][j]);
  55. 			}
  56. 		}
  57. 		numb(k,y+1);
  58. 	}
  59.  
  60. }
  61.  
  62. long long ans(int n,int k)
  63. {
  64. 	if(dp[n][k]!=-1)
  65. 		return dp[n][k];
  66. 	if(k==1)
  67. 		return dp[n][k]=1;
  68. 	long long an=0;
  69. 	for(int i=0;i<w[n].size();i++)
  70. 	{
  71. 		an+=ans(n/w[n][i],k-1);
  72. 		an%=1000000007;
  73. 	}
  74. 	return dp[n][k]=an;
  75. }
  76.  
  77. int main() 
  78. {
  79. 	f(50);
  80. 	int y;
  81. 	int n,k;
  82. 	cin>>n>>k;
  83. 	/*Find prime factorization*/
  84. 	for(int i=2;i<=2000;i++)
  85. 	{
  86. 		y=i;
  87. 		for(int j=0;j<primes.size()&&primes[j]*primes[j]<=y;j++)
  88. 		{
  89. 			if(i%primes[j]==0)
  90. 			{
  91. 				v[i].second.push_back(primes[j]);
  92. 				while(y%primes[j]==0)
  93. 				{
  94. 					y/=primes[j];
  95. 					v[i].first[primes[j]]++;
  96. 				}
  97. 			}
  98. 		}
  99. 		if(y!=1)
  100. 		{
  101. 			v[i].second.push_back(y);
  102. 			v[i].first[y]++;
  103. 		}
  104. 	}
  105. 	/*generate factors as per prime factors*/
  106. 	w[1].push_back(1);
  107. 	for(int i=2;i<=2000;i++)
  108. 	{
  109. 		w[i].push_back(1);
  110. 		numb(i,0);
  111. 	}
  112. 	for(int i=0;i<=n;i++)
  113. 	{
  114. 		for(int j=0;j<=k;j++)
  115. 			dp[i][j]=-1;
  116. 	}
  117. 	/*answer is sum of dp[i][k] values for 1<=i<=n */
  118. 	long long as=0;
  119. 	for(int i=1;i<=n;i++)
  120. 	{
  121. 		as+=ans(i,k);
  122. 		as%=1000000007;
  123. 	}
  124. 	cout<<as;
  125. 	return 0;
  126. }
Success #stdin #stdout 0.12s 41856KB
comments (?)
stdin
copy 
1478 194
stdout
copy 
312087753
https://ideone.com/ZbUdey
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!