{"raw_statement":[{"iden":"statement","content":"Arpa has found a list containing _n_ numbers. He calls a list bad if and only if it is not empty and _gcd_ (see notes section for more information) of numbers in the list is 1.\n\nArpa can perform two types of operations:\n\n*   Choose a number and delete it with cost _x_.\n*   Choose a number and increase it by 1 with cost _y_.\n\nArpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number.\n\nHelp Arpa to find the minimum possible cost to make the list good."},{"iden":"input","content":"First line contains three integers _n_, _x_ and _y_ (1 ≤ _n_ ≤ 5·105, 1 ≤ _x_, _y_ ≤ 109) — the number of elements in the list and the integers _x_ and _y_.\n\nSecond line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the elements of the list."},{"iden":"output","content":"Print a single integer: the minimum possible cost to make the list good."},{"iden":"examples","content":"Input\n\n4 23 17\n1 17 17 16\n\nOutput\n\n40\n\nInput\n\n10 6 2\n100 49 71 73 66 96 8 60 41 63\n\nOutput\n\n10"},{"iden":"note","content":"In example, number 1 must be deleted (with cost 23) and number 16 must increased by 1 (with cost 17).\n\nA _gcd_ (greatest common divisor) of a set of numbers is the maximum integer that divides all integers in the set. Read more about gcd [here](https://en.wikipedia.org/wiki/Greatest_common_divisor)."}],"translated_statement":[{"iden":"statement","content":"Arpa 找到了一个包含 #cf_span[n] 个数字的列表。他称一个列表为“坏的”，当且仅当它非空且列表中数字的 _gcd_（详见注释部分）为 #cf_span[1]。\n\nArpa 可以执行两种操作：\n\nArpa 可以对任意多个数字应用这些操作，并且允许对同一个数字无限次应用第二种操作。\n\n帮助 Arpa 找到使列表变为“好的”所需的最小代价。\n\n第一行包含三个整数 #cf_span[n], #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ n ≤ 5·105], #cf_span[1 ≤ x, y ≤ 109]）— 列表中元素的个数以及整数 #cf_span[x] 和 #cf_span[y]。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 106]）— 列表的元素。\n\n请输出一个整数：使列表变为“好的”所需的最小可能代价。\n\n在示例中，数字 #cf_span[1] 必须被删除（代价为 #cf_span[23]），数字 #cf_span[16] 必须增加 #cf_span[1]（代价为 #cf_span[17]）。\n\n一组数字的 _gcd_（最大公约数）是能整除集合中所有整数的最大整数。更多关于 gcd 的信息请参见此处。\n\n"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ n ≤ 5·105], #cf_span[1 ≤ x, y ≤ 109]）— 列表中元素的个数以及整数 #cf_span[x] 和 #cf_span[y]。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 106]）— 列表的元素。"},{"iden":"output","content":"请输出一个整数：使列表变为“好的”所需的最小可能代价。"},{"iden":"examples","content":"输入\n4 23 17\n1 17 17 16\n输出\n40\n\n输入\n10 6 2\n100 49 71 73 66 96 8 60 41 63\n输出\n10"},{"iden":"note","content":"在示例中，数字 #cf_span[1] 必须被删除（代价为 #cf_span[23]），数字 #cf_span[16] 必须增加 #cf_span[1]（代价为 #cf_span[17]）。一组数字的 _gcd_（最大公约数）是能整除集合中所有整数的最大整数。更多关于 gcd 的信息请参见此处。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n, x, y \\in \\mathbb{N} $, with $ 1 \\leq n \\leq 5 \\cdot 10^5 $, $ 1 \\leq x, y \\leq 10^9 $.  \nLet $ A = [a_1, a_2, \\dots, a_n] $ be a sequence of integers with $ 1 \\leq a_i \\leq 10^6 $.\n\nDefine a list as **bad** if $ \\gcd(A) = 1 $ and $ A \\neq \\emptyset $.  \nDefine a list as **good** if it is either empty or $ \\gcd(A) > 1 $.\n\nTwo operations are allowed:\n1. **Delete** any element $ a_i $ at cost $ x $.\n2. **Increment** any element $ a_i $ by 1, any number of times, at cost $ y $ per increment.\n\nLet $ c_i(k) $ denote the cost to transform $ a_i $ into $ a_i + k $ via increment operations: $ c_i(k) = k \\cdot y $, for $ k \\geq 0 $.\n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of indices of elements **retained**.  \nLet $ B = \\{ a_i + k_i \\mid i \\in S, k_i \\in \\mathbb{N}_0 \\} $ be the multiset of resulting values.\n\nThe goal is to choose $ S $ and non-negative integers $ \\{k_i\\}_{i \\in S} $ such that:\n- $ \\gcd(B) > 1 $,\n- Total cost $ = (n - |S|) \\cdot x + \\sum_{i \\in S} k_i \\cdot y $ is minimized.\n\nFind the **minimum total cost** over all such choices of $ S $ and $ \\{k_i\\} $.\n\n---\n\n**Note:** Since $ \\gcd(B) > 1 $, there must exist some prime $ p \\geq 2 $ such that $ p \\mid b $ for all $ b \\in B $.  \nThus, the problem reduces to:  \nFor each prime $ p \\leq \\max(A) + K $ (where $ K $ is the maximum number of increments we might consider),  \ncompute the minimum cost to make all retained elements divisible by $ p $,  \nthen take the minimum over all such $ p $.\n\nFor a fixed prime $ p $, for each $ a_i $:\n- The minimal number of increments to make $ a_i $ divisible by $ p $ is $ d_i(p) = (p - (a_i \\bmod p)) \\bmod p $.\n- Cost to keep $ a_i $: $ d_i(p) \\cdot y $.\n- Cost to delete $ a_i $: $ x $.\n- So, for each $ a_i $, optimal choice: $ \\min(x, d_i(p) \\cdot y) $.\n\nTotal cost for prime $ p $: $ \\sum_{i=1}^n \\min(x, d_i(p) \\cdot y) $.\n\nWe must compute this over all primes $ p $ such that $ p \\leq \\max(A) + \\left\\lfloor \\frac{x}{y} \\right\\rfloor $, since increments beyond $ \\lfloor x/y \\rfloor $ are never better than deletion.\n\nLet $ M = \\max(A) $, and let $ P $ be the set of all primes $ \\leq M + \\left\\lfloor \\frac{x}{y} \\right\\rfloor $.\n\nThen, the answer is:\n$$\n\\min_{p \\in P} \\sum_{i=1}^n \\min\\left(x, \\left( (p - (a_i \\bmod p)) \\bmod p \\right) \\cdot y \\right)\n$$\n\nAdditionally, consider the cost of deleting all elements: $ n \\cdot x $.\n\nThus, final answer:\n$$\n\\min\\left( n \\cdot x,\\ \\min_{p \\in P} \\sum_{i=1}^n \\min\\left(x, \\left( (p - (a_i \\bmod p)) \\bmod p \\right) \\cdot y \\right) \\right)\n$$","simple_statement":null,"has_page_source":false}