fork download
copy 
  1. #include<iostream>
  2. #include <bits/stdc++.h>
  3. #define ll unsigned long long
  4. #define f first
  5. #define s second
  6. #define pb push_back
  7. #define mk make_pair
  8. #define MAX 100000
  9. #define mod 1000000007
  10. #define zr 0
  11. ll n,k,M;
  12. using namespace std;
  13. ll xyp(ll x,ll y){
  14. 	if(y == 1) return x;
  15. 	if(y == 0) return 1;
  16. 	if(y % 2 == 0){
  17. 		ll p = xyp(x,y / 2);
  18. 		return (p * p) % mod;
  19. 	}
  20. 	ll p = xyp(x,(y - 1));
  21. 	return (x * (p) % mod) % mod;
  22. }
  23. ll invmod(ll x){
  24. 	return xyp(x,mod - 2);
  25. }
  26. class fraction{
  27. public:
  28. 	ll num,den;
  29. 	fraction(ll x,ll y){
  30. 		num = x;
  31. 		den = y;
  32. 	}
  33. 	fraction operator *(fraction f){
  34. 		ll NUM = num * f.num,DEN = den * f.den;
  35. 		fraction ans(NUM / __gcd(NUM,DEN),DEN / __gcd(NUM,DEN));
  36. 		return ans;
  37. 	}
  38. 	fraction operator +(fraction f){
  39. 		ll NUM = num * f.den + f.num * den,DEN = f.den * den;
  40. 		fraction ans(NUM / __gcd(NUM,DEN),DEN / __gcd(NUM,DEN));
  41. 		return ans;
  42. 	}
  43. 	fraction operator -(fraction f){
  44. 		ll NUM = num * f.den - f.num * den,DEN = f.den * den;
  45. 		fraction ans(NUM / __gcd(NUM,DEN),DEN / __gcd(NUM,DEN));
  46. 		return ans;
  47. 	}
  48. 	bool operator >(fraction f){
  49. 		return ((num * f.den) > (f.num * den));
  50. 	}
  51. 	ll moda(){
  52. 		return (num * invmod(den)) % mod;
  53. 	}
  54. 	void print(){
  55. 		//cout << num << " / " << den << "\n";
  56. 	}
  57. };
  58. fraction rec(ll m,ll count){
  59. 	if(count == M){
  60. 		fraction g(1,n + (m) * k);
  61. 		return g;
  62. 	}
  63. 	if(count > M){
  64. 		fraction q(0,1);
  65. 		return q;
  66. 	}
  67. 	fraction g(1,n + (m - 1) * k),p(n + (m - 1) * k - 1,n + (m - 1) * k);
  68. 	fraction h(1,n + m * k),j(n + m * k - 1,n + m * k);
  69. 	p = p * rec(m,count + 2);
  70. 	//cout << "p = ";
  71. 	//p.print();
  72. 	g = g + p;
  73. 	//cout << "g = ";
  74. 	//g.print();
  75. 	j = j * rec(m + 1,count + 1);
  76. 	h = h + j;
  77. 	if(g > h) return g;
  78. 	return h;
  79. }
  80. int main(){
  81. 	ios_base::sync_with_stdio(0);cin.tie(NULL);
  82. 	ll n,m;
  83. 	cin >> n >> m;
  84. 	ll mini = LLONG_MAX,su = 0,p = -1;
  85. 	vector <pair <ll,ll> > v;
  86. 	while(m % 2 == 0){
  87. 		m = m / 2;
  88. 		su++;
  89. 	}
  90. 	if(su > 0){
  91. 		v.push_back(mk(2,su));
  92. 	}
  93. 	for(int i = 3;i <= sqrt(m);i += 2){
  94. 		if(m % i == 0){
  95. 			ll sum = 0;
  96. 			while(m % i == 0){
  97. 				m = m / i;
  98. 				sum = sum + 1;
  99. 			}
  100. 			v.push_back(mk(i,sum));
  101. 		}
  102. 	}
  103. 	if(m > 2) v.push_back(mk(m,1));
  104. 	for(auto x : v){
  105. 		ll st = 0;
  106. 		ll d = 1,e = x.f;
  107. 		while(d > 0){
  108. 			d = n / e;
  109. 			st = st + d;
  110. 			// It gets over flow So be careful with way you check conditions
  111. 			if(e <= n / x.f)
  112. 				e = e * x.f; 
  113. 			else
  114. 				break;
  115. 		}
  116. 		st = st / x.s;
  117. 		mini = min(st,mini);
  118. 	}
  119. 	cout << mini << "\n";
  120. 	return 0;
  121. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/jfyHLZ
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!