Fişierul intrare/ieşire:cmmmc.in, cmmmc.outSursăONI 2010, clasa a 9-a
AutorStelian CiureaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cmmmc

Definim noţiunea de pereche ordonată, perechea de numere naturale (x, y) cu x ≤ y. Definim cel mai mic multiplu comun al unei perechi ordonate ca fiind cel mai mic multiplu comun al numerelor care formează perechea.

Se dau k numere naturale n1, n2, ..., nk.

Cerinţă

Să se determine pentru fiecare dintre numerele ni (i ∈ {1, 2, ..., k}):
a) câte perechi ordonate au cel mai mic multiplu comun egal cu ni.
b) dintre acestea, perechea ordonată care are suma minimă.

Date de intrare

Prima linie a fişierului cmmmc.in conţine un număr natural k. Următoarele k linii din acest fişier vor conţine câte un număr natural; linia i+1 va conţine numărul ni (i ∈ {1, 2, ..., k}).

Date de ieşire

Fişierul cmmmc.out va conţine k linii. Pe fiecare dintre acestea se vor afla trei numere. Cele trei numere de pe linia i vor reprezenta:

  • primul, numărul de perechi ordonate care au cel mai mic multiplu comun egal cu ni;
  • următoarele două, numerele care alcătuiesc perechea ordonată care are cel mai mic multiplu comun egal cu ni şi a căror sumă este minimă, afişate în ordine crescătoare.

Restricţii şi precizări

  • 1 ≤ k ≤ 100.
  • 1 ≤ ni ≤ 2 000 000 000.
  • Pentru 20% dintre teste, k ≤ 100 şi ni ≤ 1000.
  • Fiecare dintre cele k linii ale fişierului cmmmc.out trebuie să conţină exact trei numere separate prin câte un spaţiu; în caz contrar, soluţia se consideră greşită şi se obţin 0 puncte pentru testul respectiv. Rezolvarea corectă a cerinţei a) valorează 40% din punctajul unui test iar rezolvarea corectă a cerinţei b) 60%.

Exemplu

cmmmc.incmmmc.out
2
10
11
5 2 5
2 1 11

Explicaţie

Există cinci perechi distincte care au cel mai mic multiplu comun egal cu 10: (1, 10), (2, 10), (5, 10), (2, 5) si (10, 10). Dintre acestea perechea cu cea mai mică sumă este (2, 5).
Pentru n = 11 există două perechi ordonate care au cel mai mic multiplu comun 11: (1, 11), (11, 11). Dintre acestea perechea cu cea mai mică sumă este (1, 11).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content