Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

DIVIDEMULT2 - Բաժանիր և բազմապատկիր 2

Շարադրանք

Տրված են Q հատ թվազույգեր, որոնցից յուրաքանչյուրը չի գերազանցում N թիվը։ Յուրաքանչյուր թվազույգի համար, մյուսներից անկախ, պետք է գտնել և արտածել մեկ թիվ։ Այդ թիվը ստանալու համար հերթական (a, b) բնական թվերի զույգի հետ կարելի է կատարել հետևյալ գործողությունները․

 

  1. Ընտրել որևէ d թիվ, այնպիսին, որ a-ն բաժանվում է d-ի վրա առանց մնացորդի և (a, b) զույգը փոխարինել (a/d,b×d) զույգով։
  2. Ընտրել որևէ 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
Բացատրություն

 

  1. (2,8)→(4,4)
  2. (6,72)→(36,12)
  3. Որևէ նոր թվազույգ հնարավոր չէ ստանալ։
  4. (2,32)→(8,8)
  5. (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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.