Ամենամեծ ընդհանուր բաժանարար (GCD)
Տրված են երկու դրական ամբողջ թվերի
a և b։ Անհրաժեշտ է պարզել դրանց ամենամեծ ընդհանուր բաժանարարը։ Ամենամեծ ընդհանուր բաժանարարը այն թիվն է, որը բաժանում է և՛ a-ն, և՛ b-ն առանց մնացորդի, և բոլոր հնարավոր բաժանարարներից այն ամենամեծն է։Ուշադրություն դարձրեք, որ ցանկացած թվի և 0-ի ամենամեծ ընդհանուր բաժանարարը հենց տվյալ թիվն է։
Մուտք
Մուտքի միակ տողը պարունակում է երկու ամբողջ թիվ
a և b (0 ≤ a, b ≤ ):Ելք
Ծրագիրը պետք է տպի
a-ի և b-ի ամենամեծ ընդհանուր բաժանարարը։Օրինակներ
Մուտք | Ելք |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Բացատրություն
- 8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ ամենամեծ ընդհանուր բաժանարարը 4-ն է
- 54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ ամենամեծ ընդհանուր բաժանարարը 6-ն է
- 17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ ամենամեծ ընդհանուր բաժանարարը 1-ն է
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB