fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // Tablica początkowych liczb pierwszych.
  6. // Taka ilość wystarczy nawet dla N rzędu 10^18.
  7. int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
  8.  
  9. long long n;
  10. long long best_num = 1;
  11. long long max_div = 1;
  12.  
  13. // Funkcja rekurencyjna generująca kandydatów na liczby antypierwsze
  14. void dfs(int prime_idx, long long current_num, long long current_div, int max_exp) {
  15.  
  16.     // Jeśli znaleziona liczba ma więcej dzielników, staje się nowym kandydatem
  17.     if (current_div > max_div) {
  18.         max_div = current_div;
  19.         best_num = current_num;
  20.     } 
  21.     // Jeśli ma tyle samo dzielników, wybieramy mniejszą (wynika to z definicji)
  22.     else if (current_div == max_div && current_num < best_num) {
  23.         best_num = current_num;
  24.     }
  25.  
  26.     // Warunek zakończenia, by nie wyjść poza zakres tablicy primes
  27.     if (prime_idx >= 16) return;
  28.  
  29.     long long temp_num = current_num;
  30.  
  31.     // Zwiększamy potęgę dla aktualnej liczby pierwszej
  32.     // Zgodnie z własnością liczb antypierwszych i <= max_exp
  33.     for (int i = 1; i <= max_exp; ++i) {
  34.  
  35.         // Zabezpieczenie przed przekroczeniem limitu n oraz przed przepełnieniem zmiennej (overflow)
  36.         if (n / primes[prime_idx] < temp_num) {
  37.             break; 
  38.         }
  39.  
  40.         temp_num *= primes[prime_idx];
  41.  
  42.         // Wywołanie rekurencyjne dla kolejnej liczby pierwszej
  43.         // Liczba dzielników po domnożeniu p^i wzrasta (i+1) razy
  44.         dfs(prime_idx + 1, temp_num, current_div * (i + 1), i);
  45.     }
  46. }
  47.  
  48. int main() {
  49.     // Optymalizacja wejścia/wyjścia
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.  
  53.     if (cin >> n) {
  54.         // Zaczynamy od indeksu 0 (liczba pierwsza 2), wartości 1, 1 dzielnika 
  55.         // i arbitralnie dużego limitu wykładnika potęgi (np. 60 dla N <= 10^18)
  56.         dfs(0, 1, 1, 60);
  57.  
  58.         cout << best_num << "\n";
  59.     }
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2000000000
stdout
copy 
1396755360
https://ideone.com/wuT3Ux
language:
C++14 (gcc 8.3)
created:
1 hour 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!