Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
ABR0089B - ХБЕХ |
Сөрөг биш бүхэл тоонуудын хамгийн их ерөнхий хуваагчийг (ХИЕХ) олох Евклидийн алгоритм эдгээр тооны дараах чанарт үндэслэнэ: m ба n нь хоёулаа зэрэг тэгтэй тэнцүү биш сөрөг биш бүхэл тоонууд бөгөөд m ≥ n байг. Хэрэв n=0 бол ХИЕХ(m, n)=m, харин n ≠ 0 бол m, n ба r тоонуудын хувьд дараах тэнцэтгэл биелнэ: ХИЕХ(m, n)= ХИЕХ (n, r). Энд r: m тоог n-д хуваасны үлдэгдэл. Жишээ нь ХИЕХ(15, 6)= ХИЕХ(6, 3)= ХИЕХ(3, 0)=3. n, m натурал тоонууд өгөгдөв. Евклидын алгоритмыг ашиглан m, n тоонуудын ХБЕХ-ийг ол.(Энд Евклидийн алгоритмыг яаж хэрэглэж болох вэ?)
Input
n, m натурал тоонууд нэг мөрөнд, зайгаар тусгаарлагдан өгөгдөнө (m<2000000000, n<2000000000)
Output
ХБЕХ(n, m)-г олно
Example
Input: 26 32 Output: 416
Нэмсэн: | sw40 |
Огноо: | 2007-11-10 |
Хугацааны хязгаарлалт: | 1s |
Эх кодын хэмжээний хязгаарлалт: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Програмчлалын хэлүүд: | Бүгд дараах хэлүүдээс бусад: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR ERL FANTOM FORTH GOSU GRV JS-RHINO JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PERL6 PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Эх сурвалж: | Абрамов С. А. |