Ամենափոքր ընդհանուր բազմապատիկ (LCM)
Երկու թվերի
a և b ամենափոքր ընդհանուր բազմապատիկը (այսուհետ l) այն ամենափոքր թիվն է, որը բաժանվում է թե՛ a-ով, թե՛ b-ով: Ուստի հնարավոր է գտնել թիվ l, որի համար և , որտեղ x և y դրական ամբողջ թվեր են (2 ≤ x, y):Շատ պարզ, սակայն անարդյունավետ միջոցը կլիներ հերթով հաշվել
a-ի բազմապատիկները (1·a, 2·a, 3·a …) և ստուգել, թե արդյոք տվյալ բազմապատիկը բաժանվում է b-ով: Բայց այս ձևը կարող է չափազանց դանդաղ լինել: Օրինակ, երբ a-ն 13 է, իսկ b-ն՝ 17, ստիպված կլինենք ստուգել մինչև 17·13, որպեսզի համոզվենք, որ գտնվել է երկու թվերի ընդհանուր բազմապատիկ:Փաստորեն,
a·b-ն միշտ ընդհանուր բազմապատիկ է a-ի և b-ի համար, սակայն այն պարտադիր չէ, որ լինի ամենափոքր ընդհանուր բազմապատիկը: 13-ի և 17-ի դեպքում այն համընկնում է ամենափոքրին, սակայն օրինակ, 8-ի և 12-ի դեպքում՝ ոչ: Ընդհանրապես, a և b թվերի ամենափոքր ընդհանուր բազմապատիկը հավասար է դրանց արտադրյալը բաժանած ամենամեծ ընդհանուր բաժանարարով (gcd):Այս բանաձևի իմաստը նրանում է, որ բոլոր հնարավոր ընդհանուր պարզ արտադրիչները պետք է ներգրավված լինեն ամենափոքր ընդհանուր բազմապատիկում, իսկ ամենամեծ ընդհանուր բաժանարարի (gcd) գաղափարն այն է, որ այն հենց այդ ընդհանուր պարզ արտադրիչների արտադրյալն է: Ուստի, եթե երկու թվերի արտադրյալը բաժանենք դրանց gcd-ի վրա, «կհեռացնենք» ավելորդ կրկնությունները և կստանանք ճիշտ այն բազմապատիկը, որը պետք է:
Այսպիսով, երկու թվերի ամենափոքր ընդհանուր բազմապատիկը գտնելու համար նախ գտնում ենք երկու թվերի պարզ արտադրիչների վերլուծությունը, գտնում յուրաքանչյուր պարզ արտադրիչի ամենամեծ աստիճանը և բազմապատկում ենք այն գործակիցները, որոնք առնվազն մեկում կան:
Այստեղ
a·b արտադրյալը միավորում է երկու թվերի բոլոր պարզ արտադրիչները (միավորելով նրանց աստիճանները), իսկ gcd(a, b)-ն հանում է այդ աստիճանների նվազագույն մասը, թողնելով միայն առավելագույնը յուրաքանչյուր պարզ արտադրիչի համար: Արդյունքում ստացվում է հենց երկու թվերի ամենափոքր ընդհանուր բազմապատիկը:Մուտք
Մուտքի միակ տողում տրված են երկու ամբողջ թվեր
a և b (1 ≤ a, b ≤ ):Ելք
Ծրագիրը պետք է տպի
a և b թվերի ամենափոքր ընդհանուր բազմապատիկը:Օրինակներ
Մուտք | Ելք |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB