cmmdc

Time limit: 0.1s
Memory limit: 128MB
Input: cmmdc.in
Output: cmmdc.out

Se dă un șir a1,a2,,ana_1, a_2, \dots, a_n de numere naturale nenule.

Cerință

Să se determine răspunsul pentru una dintre următoarele cerințe:

  1. Cel mai mare divizor comun al celor nn numere.
  2. Cel mai mare divizor comun care se poate obține alegând exact n1n - 1 elemente din șir.
  3. Cel mai mare divizor comun care se poate obține alegând exact n2n - 2 elemente din șir.

Date de intrare

Fișierul de intrare cmmdc.in conține pe prima linie un număr natural TT reprezentând cerința cerută (11, 22 sau 33), pe a doua linie se află numărul natural nenul nn, iar pe următoarele nn linii se găsesc, câte un numărul pe fiecare linie, cele nn elemente ale șirului.

Date de ieșire

În fișierul cmmdc.out se va afișa răspunsul pentru cerința cerută.

Restricții și precizări

  • 2ai26312 \leq a_i \leq 2^{63} - 1 oricare 1in1 \leq i \leq n (numerele sunt de tip long long)
# Punctaj Restricții
1 16 T=1T = 1, 3n100 0003 \leq n \leq 100 \ 000 și ai50 000 000a_i \leq 50 \ 000 \ 000, pentru 1in1 \leq i \leq n
2 20 T=1T = 1 și 3n100 0003 \leq n \leq 100 \ 000
3 21 T=2T = 2 și 3n3 0003 \leq n \leq 3 \ 000
4 21 T=2T = 2 și 3n100 0003 \leq n \leq 100 \ 000
5 12 T=3T = 3 și 3n3003 \leq n \leq 300
6 10 T=3T = 3 și 3n2 0003 \leq n \leq 2 \ 000

Exemplul 1

cmmdc.in

1
5
48
40
20
16
80

cmmdc.out

4

Explicație

T=1T = 1, deci se cere determinarea celui mai mare divizor comun al celor cinci numere: 4848, 4040, 2020, 1616 și 8080.

Răspunul este 44.

Exemplul 2

cmmdc.in

2
5
48
40
20
16
80

cmmdc.out

8

Explicație

T=2T = 2, deci se rezolvă cerința 22.

Eliminând numărul 2020, rămân n1=4n - 1 = 4 numere, iar cmmdc(16,48,40,80)=8\text{cmmdc}(16, 48, 40, 80) = 8, care este și maximul posibil.

Exemplul 3

cmmdc.in

3
5
48
40
20
16
80

cmmdc.out

20

Explicație

T=3T = 3, deci se rezolvă cerința 33.

Eliminând numerele 1616 și 4848 rămân n2=3n - 2 = 3 numere, iar cmmdc(40,20,80)=20\text{cmmdc}(40, 20, 80) = 20, care este și maximul posibil.

Problem info

ID: 651

Editor: LucaLucaM

Author:

Source: OJI 2022 VI: Problema 1

Tags:

OJI 2022 VI

Log in or sign up to be able to send submissions!