{"problem":{"name":"G. Thai Lottery","description":{"content":"Borommarachathirat IV (สมเดจพระบรมราชาธราชท 4) was a ruler of the Ayutthaya Kingdom in the 16th century. Borommarachathirat IV decided to create a lottery for his subjects using dice. These are tradit","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10104G"},"statements":[{"statement_type":"Markdown","content":"Borommarachathirat IV (สมเดจพระบรมราชาธราชท 4) was a ruler of the Ayutthaya Kingdom in the 16th century. Borommarachathirat IV decided to create a lottery for his subjects using dice. These are traditional Thai dice and they may have several faces, where each face is rolled with the same probability.\n\nThe ruler demands the lottery to be perfectly fair, that is, each of his subjects must have the same probability of winning. The lottery consists of a finite number of rounds of dice rolls and, after each round, it is either decided that there is a winner or that more rounds are required. The dice rolls must follows the following rules:\n\nIt is imperative to ensure that each subject has the same chance of winning the lottery. Notice that this is not always possible. For instance, if there are 5 subjects and a single 6-face die, then it is impossible to have a fair lottery. On the other hand, with such a die one can have a fair lottery if the population size is 3, 6, 18, or 36 people, and so on.\n\nYour task in this problem is to write a program to help the ruler decide if it is possible to have a fair lottery with the available dice.\n\nThe first line has a single integer T, the number of test cases.\n\nEach test case is given in two lines. The first line has 2 integer, N and K, the amount of people and dice, respectively. The second line has K integers, the i-th integer fi is the number of faces in the i-th die.\n\n*Limits* \n\nFor each test case, print a single line containing a single character. Print _Y_ if it is possible to make the lottery; otherwise, print _N_.\n\n## Input\n\nThe first line has a single integer T, the number of test cases.Each test case is given in two lines. The first line has 2 integer, N and K, the amount of people and dice, respectively. The second line has K integers, the i-th integer fi is the number of faces in the i-th die.*Limits*   1 ≤ T ≤ 120  1 ≤ N ≤ 1018  0 ≤ K ≤ 105  The sum of K over all test cases will not exceed 6·105  1 ≤ fi ≤ 1018 \n\n## Output\n\nFor each test case, print a single line containing a single character. Print _Y_ if it is possible to make the lottery; otherwise, print _N_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- $ N_k \\in \\mathbb{Z}^+ $: number of subjects.  \n- $ K_k \\in \\mathbb{Z}^+ $: number of dice.  \n- $ F_k = (f_{k,1}, f_{k,2}, \\dots, f_{k,K_k}) \\in (\\mathbb{Z}^+)^{K_k} $: face counts of the dice.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. $ 1 \\le N_k \\le 10^9 $  \n3. $ 1 \\le K_k \\le 10 $  \n4. $ 1 \\le f_{k,i} \\le 100 $ for all $ i \\in \\{1, \\dots, K_k\\} $  \n\n**Objective**  \nDetermine whether there exists a finite sequence of dice rolls (with replacement) using dice from $ F_k $, such that the sample space can be partitioned into $ N_k $ equally probable outcomes.  \n\nEquivalently:  \nLet $ S $ be the multiplicative semigroup generated by $ \\{f_{k,1}, f_{k,2}, \\dots, f_{k,K_k}\\} $.  \nThen output 'Y' if $ N_k $ divides some element of $ S $; otherwise output 'N'.  \n\nThat is:  \n$$\n\\exists m \\in \\mathbb{Z}^+, \\exists e_1, \\dots, e_{K_k} \\in \\mathbb{N} \\text{ such that } N_k \\mid \\prod_{i=1}^{K_k} f_{k,i}^{e_i}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10104G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}