Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int phi (int n) {
  6. int result = n;
  7. for (int i=2; i*i<=n; ++i)
  8. if (n % i == 0) {
  9. while (n % i == 0)
  10. n /= i;
  11. result -= result / i;
  12. }
  13. if (n > 1)
  14. result -= result / n;
  15. return result;
  16. }
  17.  
  18. typedef long long lint;
  19. lint p[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
  20. lint answer, cntForAnswer, N;
  21. void findMax(int index, int lastA, lint value, lint cntForValue)
  22. {
  23. if (cntForValue > cntForAnswer || (cntForValue == cntForAnswer && value < answer))
  24. {
  25. answer = value;
  26. cntForAnswer = cntForValue;
  27. }
  28. if(index == 15) return;
  29. for(int a = 1; a <= lastA; a++)
  30. {
  31. lint temp = value * p[index];
  32. // проверка на переполнение
  33. if(temp/p[index] != value) return;
  34. // если получили число больше N
  35. if(temp > N) break;
  36. value = temp;
  37. findMax(index+1, a, value, cntForValue*(a+1));
  38. }
  39. }
  40.  
  41. int main()
  42. {
  43. cin >> N;
  44. findMax(0, 64, 1, 1);
  45. cout << cntForAnswer << endl;
  46. return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement