Pares Satisfactorios

Submit solution
Points: 100 (partial)
Time limit: 2.3s
Memory limit: 256M
Author:
dcordb
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Dado un entero positivo n, halla el número de pares de enteros positivos (a, b), donde a < b, que existen tal que la ecuación x \cdot a + y \cdot b = n tenga al menos una solución (que existan enteros positivos x y y que la satisfagan).

Nota: el 0 no es un entero positivo.

Entrada

La primera y única línea de la entrada contiene el entero n \; (4 \leq n \leq 3 \cdot 10^5).

Salida

En una única línea imprima la respuesta del problema.

Ejemplos

Entrada 1
4
Salida 1
2
Entrada 2
10
Salida 2
15
Entrada 3
1234
Salida 3
16359

Explicación del primer ejemplo

Hay dos pares (a, b): (1, 2) y (1, 3).

Comments


  • 0
    PedroPabloAB  commented on June 24, 2021, 12:56 p.m.

    Intenten enviar la solución en un horario donde el nivel de tráfico de red no esté tan alto. Creo que eso podría minimizar el tiempo de compilación, creo.


    • 1
      aniervs  commented on June 24, 2021, 1:10 p.m.

      Eso no tiene que ver. El tiempo de compilación no está involucrado en la corrida del programa, ni tampoco lo está el tráfico de red.


  • 2
    josed  commented on June 24, 2021, 3:30 a.m.

    El tiempo límite fue aumentado. Desde que este problema fue creado el DMOJ ha sufrido cambios de hardware que hacen que el tiempo de ejecución sea distinto a antes.

    Lo del tiempo de ejecución variable para un mismo código es un problema conocido, se debe a ciertas rachas de inestabilidad en la plataforma donde está hospedado el sitio. Esto debe mejorar pronto cuando se haga una migración prevista del DMOJ.


  • 0
    Kanda_Yu  commented on June 24, 2021, 1:25 a.m.

    wtf?? he enviado la misma solucion varias veces y siempre me da TLE un caso diferente


  • 0
    aniervs  commented on June 23, 2021, 4:41 p.m.

    Se añadió una editorial.


  • 0
    Josue_17904  commented on June 20, 2021, 7:42 p.m.

    Cual es el valor maximo que puede tomar b ?


    • 0
      josed  commented on June 20, 2021, 9:10 p.m.

      Eso lo puedes deducir del enunciado. Nota que a, b, x y y deben ser enteros positivos.


  • 0
    dcordb  commented on Feb. 23, 2018, 7:34 p.m.

    El problema se puede hacer en O(n \sqrt n \log n), te da TLE porque lo que haces es más lento que la solución esperada. Saludos.


    • 2
      aniervs  commented on June 21, 2021, 6:19 p.m. ← edited

      Mmm..si la solución esperada es con esa complejidad temporal, entonces el tiempo límite debería ser un poco mayor. He realizado varios envíos de un mismo código (sin alterar nada) con dicha complejidad y la sentencia es variable, algunos casos en un envío son aceptados y en otros dan TLE.

      UPD: Al reemplazar un vector que creaba n veces por un arreglo estático global, el tiempo de corrida mejoró mucho, y dio AC.


    • 0
      angelmh  commented on March 28, 2018, 5:20 p.m.

      Eso se debe a algun algoritmo específico o es simplemente la complejidad maxima de fuerza bruta que se puede alcanzar?


  • 1
    angelmh  commented on Feb. 23, 2018, 1:57 p.m.

    Hola, buen dia, solo quieria saber una respuesta de SI o NO, existe una solucion a este problema distinta a la que voy a explicar ahora? Disculpen si me expreso de la forma incorrecta. Mi solucion me da TLE en la mayoria de los casos, quiero saber si existe algo para mederar este tiempo que en java no veo otra manera.

    Mi analisis es que esto se cumple si y solo si n%d==0 donde d es mcd(a,b) pero esto lo hago en O(n^2), puede ser por esto que me da TLE???