fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long int lli;
  5.  
  6.  
  7. void getPrimeFactors(lli b, vector<pair<lli,lli>> &factors ){
  8. 	pair<lli,lli> temp;
  9. 	temp.first=2;
  10. 	temp.second=0;
  11. 	while(b%2==0){
  12. 		temp.second++;
  13. 		b/=2;
  14. 	}
  15. 	if(temp.second!=0){
  16. 		factors.push_back(temp);
  17. 	}
  18. 	double sqB=sqrt(b);
  19. 	for(lli i=3; i<=sqB; i+=2){
  20. 		temp.first=i;
  21. 		temp.second=0;
  22. 		while(b%i==0){
  23. 			temp.second++;
  24. 			b/=i;
  25. 		}
  26. 		if(temp.second!=0){
  27. 			factors.push_back(temp);
  28. 		}
  29. 	}
  30. 	if(b>2){
  31. 		temp.first=b;
  32. 		temp.second=1;
  33. 		factors.push_back(temp);
  34. 	}
  35. }
  36. int main() {
  37. 	lli n,b;
  38. 	cin>>n>>b;
  39.  
  40. 	lli ans=0;
  41.  
  42. 	double sqB=sqrt(b);
  43. 	lli nFactors=0;
  44.  
  45. 	vector<pair<lli,lli>> initFactors;
  46. 	getPrimeFactors(b,initFactors);
  47.  
  48. 	/*vector<pair<lli,lli>>::iterator it;
  49. 	for(it=initFactors.begin(); it!=initFactors.end(); it++){
  50. 		cout<<(*it).first<<" "<<(*it).second<<"\n";
  51. 	}*/
  52.  
  53. 	vector<lli> countFactors(initFactors.size(),0);
  54. 	lli i=0;
  55. 	vector<pair<lli,lli>>::iterator it;
  56. 	for(it=initFactors.begin(); it!=initFactors.end(); it++){
  57. 		lli tempN=n;
  58. 		while(tempN>0){
  59. 			countFactors[i]+=tempN/(*it).first;
  60. 			tempN/=(*it).first;
  61. 		}	
  62. 		i++;
  63. 	}
  64. 	lli min=1000000000000000000;
  65. 	for(lli i=0; i<countFactors.size(); i++){
  66. 		lli temp=countFactors[i]/initFactors[i].second;
  67. 		if(min>temp)
  68. 			min=temp;
  69. 	}
  70. 	cout<<min;
  71. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1000000000000000000 999999999989
stdout
copy 
1000000
https://ideone.com/xxqOtv
language:
C++14 (gcc 8.3)
created:
5 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!