ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1118. Нетривиальные числа

AC IN 0.001 and 420kb
Послано buyolitsez 20 мар 2019 19:51
#include <bits/stdc++.h>

//#pragma optimize("O2")

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

//#define int long long

bool check(int n) {
    if(n == 1)
        return true;
    if(n % 2  == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
        if(n % i == 0)
            return false;
    return true;
}

double sum(int n) {
    int count = 1;
    for (int i = 2; i * i <= n; ++i)
        if(n % i == 0)
            count += i + n / i;
    return (double)count / (double)n;
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int a, b;
   cin >> a >> b;
   if(a == 1) {
       cout << 1;
       return 0;
   }
   int pos = -1;
   double score = 100000;
   for (int i = b; i >= a; --i) {
       double f =  sum(i);
       if(check(i)) {
           if(score > f)
                cout << i;
            else
                cout << pos;
            return 0;
       }
       if(score > f) {
           score = f;
           pos = i;
       }
   }
   cout << pos;
   return 0;
}