| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
DIVIDEMULT2 - Բաժանիր և բազմապատկիր 2 |
Շարադրանք
Տրված են Q հատ թվազույգեր, որոնցից յուրաքանչյուրը չի գերազանցում N թիվը։ Յուրաքանչյուր թվազույգի համար, մյուսներից անկախ, պետք է գտնել և արտածել մեկ թիվ։ Այդ թիվը ստանալու համար հերթական (a, b) բնական թվերի զույգի հետ կարելի է կատարել հետևյալ գործողությունները․
- Ընտրել որևէ d թիվ, այնպիսին, որ a-ն բաժանվում է d-ի վրա առանց մնացորդի և
(a, b)զույգը փոխարինել(a/d,b×d)զույգով։ - Ընտրել որևէ d թիվ, այնպիսին, որ b-ն բաժանվում է d-ի վրա առանց մնացորդի և
(a, b)զույգը փոխարինել(a×d,b/d)զույգով։
Այս երկու գործողություններից յուրաքանչյուրը թույալտրվում է կիրառել որքան ուզեք։ Արդյունքում հնարավոր է ստանալ բազմաթիվ թվազույգեր։ Այդ թվազույգերից յուրաքանչյուրն ունի իր ամենամեծ ընդհանուր բաժանարարը (ԱԸԲ)։ Պահանջվում է պարզել, թե առավելագույնը ինչ ԱԸԲ է հնարավոր ստանալ։
Մուտքային տվյալներ
Առաջին տողում տրված են N (1 ≤ N ≤ 2×106) և Q (1 ≤ Q ≤ 500 000) դրական ամբողջ թվերը՝ թվազույգերին պատկանող թվերի մեծագույն արժեքը և թվազույգերի քանակը։
Հաջորդ Q տողերից յուրաքանչյուրում տրված են երկու դրական ամբողջ a և b թվեր, որոնք չեն գերազանցում N-ը։
Ելքային տվյալներ
Ելքում պետք է արտածել Q հատ թիվ, որոնցից i-րդը պետք է հավասար լինի մուտքում տրված i-րդ թվազույգից նշված կանոնների կիրառման արդյունքում ստացվող թվազույգերի ԱԸԲ-ներից մեծագույնին։
Օրինակ
| Մուտք | Ելք |
|---|---|
|
100 5 2 8 6 72 38 39 2 32 9 8 |
4 12 1 8 6 |
Բացատրություն
- (2,8)→(4,4)
- (6,72)→(36,12)
- Որևէ նոր թվազույգ հնարավոր չէ ստանալ։
- (2,32)→(8,8)
- (9,8)→(3,24)→(6,12)
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2023-01-28 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Մարզային փուլ, 2022-23 |
RSS