{"problem":{"name":"GCD or MIN","description":{"content":"There are $N$ integers $A_1, A_2, A_3, \\dots, A_N$ written on a blackboard.   You will do the following operation $N - 1$ times: *   Choose two numbers written on the blackboard and erase them. Let $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc191_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ integers $A_1, A_2, A_3, \\dots, A_N$ written on a blackboard.  \nYou will do the following operation $N - 1$ times:\n\n*   Choose two numbers written on the blackboard and erase them. Let $x$ and $y$ be the erased numbers. Then, write $\\gcd(x, y)$ or $\\min(x, y)$ on the blackboard.\n\nAfter $N - 1$ operations, just one integer will remain on the blackboard. How many possible values of this number are there?\n\n## Constraints\n\n*   $2 \\le N \\le 2000$\n*   $1 \\le A_i \\le 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $A_3$ $\\dots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc191_f","tags":[],"sample_group":[["3\n6 9 12","2\n\nThe possible values of the last remaining number are $3$ and $6$.  \nWe will have $3$ in the end if, for example, we do as follows:\n\n*   choose $9, 12$ and erase them from the blackboard, then write $\\gcd(9, 12) = 3$;\n*   choose $6, 3$ and erase them from the blackboard, then write $\\min(6, 3) = 3$.\n\nAlso, we will have $6$ in the end if, for example, we do as follows:\n\n*   choose $6, 12$ and erase them from the blackboard, then write $\\gcd(6, 12) = 6$;\n*   choose $6, 9$ and erase them from the blackboard, then write $\\min(6, 9) = 6$."],["4\n8 2 12 6","1\n\n$2$ is the only number that can remain on the blackboard."],["7\n30 28 33 49 27 37 48","7\n\n$1$, $2$, $3$, $4$, $6$, $7$, and $27$ can remain on the blackboard."]],"created_at":"2026-03-03 11:01:13"}}