{"problem":{"name":"C. НОД на отрезке","description":{"content":"Вам дан массив a1, a2, ..., an, состоящий из целых положительных чисел. Так же вам даны m запросов вида li, ri. В ответ на i-ый запрос нужно вывести наибольший общий делитель чисел ali, ali + 1, ..., ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10026C"},"statements":[{"statement_type":"Markdown","content":"Вам дан массив a1, a2, ..., an, состоящий из целых положительных чисел. Так же вам даны m запросов вида li, ri. В ответ на i-ый запрос нужно вывести наибольший общий делитель чисел ali, ali + 1, ..., ari.\n\nВ первой строке записаны два целых числа n, m (1 ≤ n, m ≤ 50000). Во второй строке записан массив a1, a2, ..., an (1 ≤ ai ≤ 109). В следующих m строках записаны пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n) — запросы.\n\nВ ответ на каждый запрос выведите наибольший общий делитель элементов массива из соответствующего отрезка.\n\n## Входные Данные\n\nВ первой строке записаны два целых числа n, m (1 ≤ n, m ≤ 50000). Во второй строке записан массив a1, a2, ..., an (1 ≤ ai ≤ 109). В следующих m строках записаны пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n) — запросы.\n\n## Выходные Данные\n\nВ ответ на каждый запрос выведите наибольший общий делитель элементов массива из соответствующего отрезка.\n\n## Примеры\n\nВходные данные10 1318 12 18 12 12 15 18 9 18 64 910 108 106 62 64 57 91 71 51 13 46 76 9Выходные данные3631531293618633\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the length of the array and the number of queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i \\in \\mathbb{Z}^+ $.  \nLet $ Q = \\{(l_j, r_j) \\mid j \\in \\{1, \\dots, m\\}\\} $ be the set of queries, where $ 1 \\le l_j \\le r_j \\le n $.\n\n**Constraints**  \n1. $ 1 \\le n, m \\le 50000 $  \n2. $ 1 \\le a_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\le l_j \\le r_j \\le n $ for all $ j \\in \\{1, \\dots, m\\} $\n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, m\\} $, compute:  \n$$\n\\gcd(a_{l_j}, a_{l_j+1}, \\dots, a_{r_j})\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10026C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}