Ամենամեծ ընդհանուր բաժանարար (GCD) - թվերի հատվածի վրա
Ձեզ տրված է
n ամբողջ թիվը, և ձեզ խնդրում են պատասխանել q հարցման։ Ամեն հարցում իրենից ներկայացնում է երկու թիվ՝ l և r։ Անհրաժեշտ է պարզել, [l, r] միջակայքում գտնվող բոլոր թվերի ամենամեծ ընդհանուր բաժանարար:Մուտք
Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ
n (1 ≤ n ≤ 5000) և q (1 ≤ q ≤ 10):Հաջորդ տողը պարունակում է
n ամբողջ թվեր, որոնք ներկայացնում են են զանգվածը (1 ≤ ≤ ):Հաջորդ
q տողերում տրված են հարցումները, որոնք սահմանում են տարբեր միջակայքերը (0 ≤ ≤ < n):Ելք
Ծրագիրը պետք է տպի
[l, r] միջակայքում գտնվող բոլոր թվերի ամենամեծ ընդհանուր բաժանարարը։Օրինակներ
Մուտք | Ելք |
8 4
12 24 198 64 9 8 4 100
0 1
1 2
1 4
5 7 | 12 6 1 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB