Բաժանիր և բազմապատկիր
Տրված են 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 ≤ ) և 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)
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (17 միավոր)
որտեղ-ն և-ն պարզ թվեր են։
- Ենթախնդիր 2 (11 միավոր) , որտեղ -ն դրական ամբողջ թիվ է
- Ենթախնդիր 3 (25 միավոր) N ≤ 10 000, Q ≤ 1 000:
- Ենթախնդիր 4 (23 միավոր) N ≤ 100 000, Q ≤ 100 000:
- Ենթախնդիր 5 (24 միավոր) Լրացուցիչ սահմանափակումներ չկան:
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 3 MB