#include <iostream>
#include <limits>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int lowest_trivia_number (int I, int J) {
    double min_trivia = std::numeric_limits<double>::max();
    int res = 0;
    for (int i = I; i <= J; i++) {
        int sum_of_own_denominators = 1;
        for(int j = 2; j <= std::sqrt(i); j++){
            if(i % j == 0) {
                sum_of_own_denominators += j;
                if(j != i / j) {
                    sum_of_own_denominators += i / j;
                }
            }
        }

        double cur_trivia = sum_of_own_denominators/i;
        if (cur_trivia < min_trivia) {
            min_trivia = cur_trivia;
            res = i;
        }
    }
    return res;
}

int main() {
    int I, J;

    std::cin >> I >> J;
    if(I == 1) {
        std::cout << 1;
        return 0;
    }

    int largestPrime = -1;

    for (int num = J; num >= I; num--) {
        if (isPrime(num)) {
            largestPrime = num;
            break;
        }
    }

    if (largestPrime != -1) {
        std::cout << largestPrime << std::endl;
    } else {
        std::cout << lowest_trivia_number(I, J);
    }

    return 0;
}

If you look at the statement, it says "Triviality of a natural number N is the ratio of the sum of all its proper divisors to the number itself. Recall that a proper divisor of a natural number is the divisor that is strictly less than the number.". Therefore, triviality of 1 should be 0 / 1 == 0, since 1 doesn't have any divisor strictly less than itself. However, I couldn't get an AC (WA4) until I changed the line
if (I == 1) ans = 0
to
if (I == 1) ans = 1.
So, either the statement or the tests are broken.

Edited by author 05.08.2022 19:55

Edited by author 05.08.2022 19:55

I have WA on test 7. What i need to do?

Output is EndPoint. EndPoint is simple.

Use long long

What is test 5? I can give my code(It's not working), runtime error(access violation)

Good afternoon! I am a programmer-beginner. I have written the code for this task on c++, but the time limit is exceeded on the second test!
The code is this: (https://ideone.com/Rh98zQ)

#include <iostream>
using namespace std;

float ghj(int a)
{int m;
m=0;
for(int l=1; l<a; l++)
{if(a%l==0)
{m=m+l;}}
float c=(float(int(m)));
float b=c/a;
return b;}

int main() {
int i,j;
cin >> i >> j;
float p=ghj(i);
int n=i;
for(int o=i; o<=j; o++)
{if(ghj(o)<p)
{p=ghj(o);
n=o;}}
cout << n;
return 0;
}

Tell me, please, how can I optimize the code?

#include <iostream>
using namespace std;
int main() {
    long long i, j, iDel; long long biggestV = 9999999, biggestDel = 9999999;
    cin >> i >> j;
    if (i == 1) {
        cout << 1;
        return 0;
    }
    else if (i == j) {
        cout << i;
        return 0;
    }
    else if (i + 1 == j) {
        cout << (j % 2 != 0 ? j : i);
        return 0;
    }
    for (long long iV = j % 2 != 0 ? j : j-1; iV >= i; iV -= 2) {
        for (iDel = j / 3 + 1; iDel >= 1; iDel--) {
            if (iV%iDel == 0) {
                if (iDel < biggestDel) {
                    biggestDel = iDel;
                    biggestV = iV;
                }
                break;
            }
        }
        if (iDel == 1) {
            cout << iV;
            return 0;
        }
    }
    cout << biggestV;
}

----
ll l,r;
    cin >> l >> r;
    if(l==1){
        cout << 1;
        return 0;
    }
    if(l == r){
        cout << l;
        return 0;
    }
    ll n = 1e6+2;
    vector<bool> prime(n+1,1);
    prime[0]=prime[1] = 0;
    for( ll i =2; i*i <= n; i++)
    {
        if(prime[i])
        {
            for(ll j = i*i; j <= n; j+=i)
                prime[j]=0;
        }
    }

    for(ll i = r; i >= l; i--){
        if(prime[i])
        {

            cout << i;
            return 0;
        }
    }
    double mx =1e11;
    ll ans = 0;
    for(ll i = r; i >= l; i--){

        if(i % 2 == 0)
            continue;


        double suma = 1;
        for(ll k = 2; k*k <= i; k++){

            if( i % k == 0 ){
                suma += k;
                if(i/k != k){

                    suma += (i/k);
                }
            }
        }

        double q=(suma)/(i);


        if( q < mx){
            mx = q;
            ans = i;
        }

    }
    cout << ans;
    return 0;
----

I used the sieve of Eratosthenes to find prime numbers. If I have not found prime numbers on the interval [l; r], then I iterate over all numbers with [l; r]. I go through the divisors (sqrt (i)). I calculate the minimum. What's wrong? WA 11. Google translator, sorry.

WHAT IS TEST 8

Judjes tell me after you read my message, I will delete
an AC program.

Here is th 1st program it got WA#3:

[Program was deleted by author, beacuse it got AC =)]
[Thx Vladimir! Judges if you need it, I can post it.]


Here is 2nd program it got AC:

[Program was deleted by author]
[Judges if you need it, I can post that code for a while]

Here is one test:
318 330

Correct answer is 323 (Triviality(323)=0.114551)
AC programs answer for this tests was :
324 (Triviality(324)=1.619195)

It means that AC program gave incorrect answer, but
program which got WA#3 gave correct answer!!!
It's shameful!!!

Edited by author 20.01.2006 20:49

Edited by author 21.01.2006 02:45

Why is triviality(1)=1?

assc

Edited by author 20.03.2019 19:54

My code gives true answers for all tests but when I send problem it gives WA in test 3. please write answer.

[code deleted]

Edited by moderator 19.11.2019 23:40

I always get WA on test 4,who can give me the testdata of test4.Help me!Thank you.

#include <iostream>

using namespace std;
bool prime(long long n);


int main()
{
    long long a,odd, i, j, nice,b;
    cin >> a >> b;
    nice=0;
    if (a%2==1) {odd=a;} else {odd=a+1;}
    for (i=b; i>a; i--)
    {
       if (prime(i))
       {
           nice=i;
           break;
       }
    }

    if ((a==1 or nice==0) and b!=a) { cout << odd;}
    else if (b==a) {cout << a;}
    else
    if (nice) {cout << nice << endl;}
    return 0;
}

bool prime(long long n)
{
    bool w;
    w=n==2;
    if (!w and n%2)
    {
        w=1;
        for (int i=3; i*i<=n; i+=2)
        {
            if (n%i==0)
            {
                w=0 ;
                break;
            }
        }
    }
    if (w)
    {
        return 1;
    }
    else return 0;
}

Calculates sum of divisors.
O(lim * log(lim)).
for(int i = 2; i <= lim; ++i){
    ++s[i];
    for(int j = i + i; j <= lim; j += i)
        s[j] += i;
}

[code deleted]

Edited by moderator 19.11.2019 23:41

First, triviality of 1 is 0.
Second, we can judge number i from 2 to 1000000, if i is a prime number, then prime[i] is true.
Third, we traversal i from b to a, because if j>i and prime[j]==true, prime[i]==true, we can get 1/j<1/i.
if we get prime[i]==true,just output it and break.
if we can not get such a number, calculate triviality of i and output the minimum.

Thus, we can get AC with a little time spended,but larger memory.

My English is poor, if you cannot understand me, I would say sorry for it.^__^