Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int phi (int n) {
- int result = n;
- for (int i=2; i*i<=n; ++i)
- if (n % i == 0) {
- while (n % i == 0)
- n /= i;
- result -= result / i;
- }
- if (n > 1)
- result -= result / n;
- return result;
- }
- typedef long long lint;
- lint p[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
- lint answer, cntForAnswer, N;
- void findMax(int index, int lastA, lint value, lint cntForValue)
- {
- if (cntForValue > cntForAnswer || (cntForValue == cntForAnswer && value < answer))
- {
- answer = value;
- cntForAnswer = cntForValue;
- }
- if(index == 15) return;
- for(int a = 1; a <= lastA; a++)
- {
- lint temp = value * p[index];
- // проверка на переполнение
- if(temp/p[index] != value) return;
- // если получили число больше N
- if(temp > N) break;
- value = temp;
- findMax(index+1, a, value, cntForValue*(a+1));
- }
- }
- int main()
- {
- cin >> N;
- findMax(0, 64, 1, 1);
- cout << cntForAnswer << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement