.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » euclid

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
euclid


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 1MB

Este binecunoscut algoritmul de calcul al celui mai mare divizor comun (cmmdc) cu algoritmul lui Euclid prin împărţiri repetate. Conform acestui algoritm cmmdc a două numere naturale nenule a şi b se calculează păstrând restul împărţirii, şi reluând împărţirea cu vechiul împărţitor şi vechiul rest. Algoritmul se va termina când restul împărţirii devine zero. Cel mai mare divizor comun al celor două numere a şi b va fi ultimul împărţitor.
Pentru calculul celui mai mare divizor comun al perechii (16,22) se vor efectua succesiv împărţirile:



Vom numi un “pas” o operaţie de împărţire ce intervine în calculului cmmdc. Se observă că pentru determinarea cmmdc(16,22)=2 au fost necesari 5 paşi.

Cerinţă

Cunoscând valoarea unui număr natural n, realizaţi un program care determină o pereche de numere naturale (a,b) mai mici sau egale cu n, al căror cmmdc se obţine într-un număr maxim de paşi. Dacă există mai multe perechi (x,y) cu această proprietate se va afişa cea minimă. Spunem că perechea (a,b) este mai mică decât (x,y), dacă a<x sau a=x şi b<y.

Date de intrare

Fişierul text euclid.in conţine un singur număr natural n.

Date de ieşire

Fişierul text euclid.out va conţine pe prima linie numărul maxim de paşi determinat. A doua linie va conţine un număr natural a reprezentând primul număr al perechii minime identificate, iar pe a treia linie se va scrie numărul b reprezentând al doilea număr din pereche.

Restricţii

4 <= n <= 10200

Exemple

euclid.ineuclid.outExplicaţii
8 5 5 8 Numărul maxim de paşi pentru oricare pereche de numere mai mici egale cu 8 este 5. Perechea (5,8) este minimă cu această proprietate.
12345678910 48 4807526976 7778742049 Numărul maxim de paşi pentru oricare pereche de numere mai mici egale cu 12345678910 este 48.
Perechea (4807526976,7778742049) este minimă cu această proprietate.

autor: Prof. Zoltan Szabo
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot IS 2008: arbnr, center, pitici, sirag1, cod1, tabara, desen1, munte, pipe, sport, stive, bombe, shgraf, paintball, arb, pav
De acelaşi autor: balanta, bonuri, cub, magic, magic2, munte, banda, biliard, fractie1, fotbal, arctir, orientare, rege, fibo1, piatra, war, aritm, ssmax, sirmax, ikebana, punctfix, domino2, lant1, parc1, cubulete, biperm, triunghi6, stiva1
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Despre numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, mutare, munte1, bifo, banda10, sg1, cutii, zumzi, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Despre Fibonacci: fib, grupe, descfib, fibo, gramada, vanatoare, sirul, fibo1, taler, aliniere, subm, flori2, prime2
Chestionare recomandate
surse trimise | ajutor