{"problem":{"name":"B. Nastya Studies Informatics","description":{"content":"Today on Informatics class Nastya learned about GCD and LCM (see links below). Nastya is very intelligent, so she solved all the tasks momentarily and now suggests you to solve one of them as well. W","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF992B"},"statements":[{"statement_type":"Markdown","content":"Today on Informatics class Nastya learned about GCD and LCM (see links below). Nastya is very intelligent, so she solved all the tasks momentarily and now suggests you to solve one of them as well.\n\nWe define a pair of integers (_a_, _b_) _good_, if _GCD_(_a_, _b_) = _x_ and _LCM_(_a_, _b_) = _y_, where _GCD_(_a_, _b_) denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of _a_ and _b_, and _LCM_(_a_, _b_) denotes the [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of _a_ and _b_.\n\nYou are given two integers _x_ and _y_. You are to find the number of _good_ pairs of integers (_a_, _b_) such that _l_ ≤ _a_, _b_ ≤ _r_. Note that pairs (_a_, _b_) and (_b_, _a_) are considered different if _a_ ≠ _b_.\n\n## Input\n\nThe only line contains four integers _l_, _r_, _x_, _y_ (1 ≤ _l_ ≤ _r_ ≤ 109, 1 ≤ _x_ ≤ _y_ ≤ 109).\n\n## Output\n\nIn the only line print the only integer — the answer for the problem.\n\n[samples]\n\n## Note\n\nIn the first example there are two suitable _good_ pairs of integers (_a_, _b_): (1, 2) and (2, 1).\n\nIn the second example there are four suitable _good_ pairs of integers (_a_, _b_): (1, 12), (12, 1), (3, 4) and (4, 3).\n\nIn the third example there are _good_ pairs of integers, for example, (3, 30), but none of them fits the condition _l_ ≤ _a_, _b_ ≤ _r_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"今天在信息学课上，Nastya 学习了 GCD 和 LCM（见下方链接）。Nastya 非常聪明，她立刻解决了所有题目，现在她建议你也来解决其中一道。\n\n我们定义一对整数 #cf_span[(a, b)] 为 _good_，当且仅当 #cf_span[GCD(a, b) = x] 且 #cf_span[LCM(a, b) = y]，其中 #cf_span[GCD(a, b)] 表示 #cf_span[a] 和 #cf_span[b] 的最大公约数，#cf_span[LCM(a, b)] 表示 #cf_span[a] 和 #cf_span[b] 的最小公倍数。\n\n给你两个整数 #cf_span[x] 和 #cf_span[y]。你需要找出满足 #cf_span[l ≤ a, b ≤ r] 的 _good_ 整数对 #cf_span[(a, b)] 的数量。注意，如果 #cf_span[a ≠ b]，则对 #cf_span[(a, b)] 和 #cf_span[(b, a)] 被视为不同。\n\n输入仅一行包含四个整数 #cf_span[l, r, x, y]（#cf_span[1 ≤ l ≤ r ≤ 10^9]，#cf_span[1 ≤ x ≤ y ≤ 10^9]）。\n\n请在唯一一行输出一个整数 —— 本题的答案。\n\n在第一个例子中，有两个合适的 _good_ 整数对 #cf_span[(a, b)]：#cf_span[(1, 2)] 和 #cf_span[(2, 1)]。\n\n在第二个例子中，有四个合适的 _good_ 整数对 #cf_span[(a, b)]：#cf_span[(1, 12)]、#cf_span[(12, 1)]、#cf_span[(3, 4)] 和 #cf_span[(4, 3)]。\n\n在第三个例子中，存在 _good_ 整数对，例如 #cf_span[(3, 30)]，但没有一对满足条件 #cf_span[l ≤ a, b ≤ r]。\n\n## Input\n\n输入仅一行包含四个整数 #cf_span[l, r, x, y]（#cf_span[1 ≤ l ≤ r ≤ 10^9]，#cf_span[1 ≤ x ≤ y ≤ 10^9]）。\n\n## Output\n\n请在唯一一行输出一个整数 —— 本题的答案。\n\n[samples]\n\n## Note\n\n在第一个例子中，有两个合适的 _good_ 整数对 #cf_span[(a, b)]：#cf_span[(1, 2)] 和 #cf_span[(2, 1)]。在第二个例子中，有四个合适的 _good_ 整数对 #cf_span[(a, b)]：#cf_span[(1, 12)]、#cf_span[(12, 1)]、#cf_span[(3, 4)] 和 #cf_span[(4, 3)]。在第三个例子中，存在 _good_ 整数对，例如 #cf_span[(3, 30)]，但没有一对满足条件 #cf_span[l ≤ a, b ≤ r]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ x, y $ be given positive integers. A pair $ (a, b) $ is *good* if:\n\n$$\n\\gcd(a, b) = x \\quad \\text{and} \\quad \\mathrm{lcm}(a, b) = y.\n$$\n\nIt is known that for any positive integers $ a, b $:\n\n$$\na \\cdot b = \\gcd(a, b) \\cdot \\mathrm{lcm}(a, b) = x \\cdot y.\n$$\n\nLet $ a = x \\cdot a' $, $ b = x \\cdot b' $, where $ \\gcd(a', b') = 1 $. Then:\n\n$$\n\\mathrm{lcm}(a, b) = x \\cdot a' \\cdot b' = y \\quad \\Rightarrow \\quad a' \\cdot b' = \\frac{y}{x}.\n$$\n\nThus, a necessary condition is that $ x \\mid y $. If $ x \\nmid y $, then no good pairs exist.\n\nAssume $ x \\mid y $. Let $ k = \\frac{y}{x} $. Then we seek pairs of coprime positive integers $ (a', b') $ such that:\n\n$$\na' \\cdot b' = k, \\quad \\gcd(a', b') = 1.\n$$\n\nEach such pair $ (a', b') $ corresponds to a good pair $ (a, b) = (x a', x b') $.\n\nNote: Since $ \\gcd(a', b') = 1 $ and $ a' b' = k $, the pair $ (a', b') $ must consist of two coprime divisors of $ k $ whose product is $ k $. This occurs if and only if $ a' $ and $ b' $ are complementary divisors of $ k $ with no common prime factors — i.e., $ a' $ is a divisor of $ k $ such that $ \\gcd(a', k/a') = 1 $. This is equivalent to $ a' $ being a **unitary divisor** of $ k $, or more simply: $ a' $ must be a divisor of $ k $ such that $ \\gcd(a', k/a') = 1 $, which is always true if we take $ a' $ to be a divisor of $ k $ composed of a subset of the prime factors of $ k $, and $ b' = k/a' $ takes the complementary subset. Since $ \\gcd(a', b') = 1 $, this holds **if and only if** $ a' $ and $ b' $ are coprime, which is equivalent to $ a' $ being a divisor of $ k $ with no square factors shared with $ b' $ — but since their product is $ k $, this condition holds **exactly when** $ a' $ is a divisor of $ k $ such that $ \\gcd(a', k/a') = 1 $, which is equivalent to $ a' $ being a **square-free divisor** of $ k $ that includes a subset of the distinct prime factors of $ k $, and $ b' $ includes the rest.\n\nActually, a simpler characterization: the number of unordered coprime pairs $ (a', b') $ with $ a' b' = k $ is $ 2^{\\omega(k)} $, where $ \\omega(k) $ is the number of distinct prime factors of $ k $. But since $ (a', b') $ and $ (b', a') $ are considered distinct when $ a' \\ne b' $, and we want **ordered** pairs, then the total number of **ordered** coprime pairs $ (a', b') $ with $ a' b' = k $ is exactly $ 2^{\\omega(k)} $, because for each prime factor of $ k $, we assign it entirely to $ a' $ or to $ b' $, and since $ \\gcd(a', b') = 1 $, no prime can be split.\n\nThus, the number of **ordered** good pairs $ (a, b) $ with $ \\gcd(a,b)=x $, $ \\mathrm{lcm}(a,b)=y $ is $ 2^{\\omega(k)} $, where $ k = y/x $, **provided** $ x \\mid y $.\n\nBut we are constrained by $ l \\le a, b \\le r $.\n\nSo the algorithm is:\n\n---\n\n**Given**: $ l, r, x, y $\n\n**Step 1**: If $ x \\nmid y $, output 0.\n\n**Step 2**: Let $ k = y / x $.\n\n**Step 3**: Find all **ordered** pairs $ (a', b') $ such that:\n- $ a' \\cdot b' = k $,\n- $ \\gcd(a', b') = 1 $.\n\nEach such pair gives $ a = x a' $, $ b = x b' $.\n\n**Step 4**: For each such pair $ (a', b') $, check if:\n$$\nl \\le x a' \\le r \\quad \\text{and} \\quad l \\le x b' \\le r.\n$$\n\nCount the number of such valid ordered pairs.\n\n---\n\nHow to generate all such $ (a', b') $?\n\nLet $ D $ be the set of divisors $ d $ of $ k $ such that $ \\gcd(d, k/d) = 1 $. For each such $ d $, the pair $ (d, k/d) $ is coprime. Since $ \\gcd(d, k/d) = 1 $, this happens if and only if $ d $ is a divisor of $ k $ that includes a subset of the distinct prime factors of $ k $, i.e., $ d $ is a **square-free divisor** composed of a subset of the prime factors of $ k $, and $ k/d $ gets the rest. But since $ k $ may have repeated prime factors, we must factor $ k $ into its **distinct** prime factors.\n\nActually, $ \\gcd(d, k/d) = 1 $ if and only if $ d $ is a divisor of $ k $ such that for every prime $ p $ dividing $ k $, $ p $ divides **either** $ d $ **or** $ k/d $, but **not both** — which is always true if we define $ d $ as a product of a subset of the distinct primes dividing $ k $, each raised to their full power in $ k $.\n\nThat is: Let $ k = \\prod_{i=1}^m p_i^{e_i} $. Then the coprime divisor pairs $ (d, k/d) $ correspond to assigning each prime power $ p_i^{e_i} $ entirely to $ d $ or to $ k/d $. So there are $ 2^m $ such ordered pairs $ (d, k/d) $, where $ m = \\omega(k) $.\n\nThus, the set of valid $ (a', b') $ is:\n\n$$\n\\left\\{ \\left( \\prod_{i \\in S} p_i^{e_i}, \\prod_{i \\notin S} p_i^{e_i} \\right) \\mid S \\subseteq \\{1, 2, \\dots, m\\} \\right\\}\n$$\n\nEach such pair is unique and ordered.\n\nSo:\n\n- Factor $ k = y/x $ into its prime factorization: $ k = \\prod_{i=1}^m p_i^{e_i} $\n- For each subset $ S \\subseteq \\{1, \\dots, m\\} $, compute:\n  $$\n  a' = \\prod_{i \\in S} p_i^{e_i}, \\quad b' = \\prod_{i \\notin S} p_i^{e_i}\n  $$\n- Compute $ a = x \\cdot a' $, $ b = x \\cdot b' $\n- Check if $ l \\le a \\le r $ and $ l \\le b \\le r $\n- Count the number of such valid pairs\n\nNote: Since $ a' \\cdot b' = k $, and $ a = x a' $, $ b = x b' $, we have $ a \\cdot b = x^2 k = x^2 \\cdot (y/x) = x y $, as expected.\n\nAlso, since $ \\gcd(a', b') = 1 $, we have $ \\gcd(a, b) = x \\cdot \\gcd(a', b') = x $, and $ \\mathrm{lcm}(a, b) = x \\cdot a' \\cdot b' = x k = y $, so the pair is good.\n\n---\n\n**Final Formal Statement:**\n\nLet $ l, r, x, y \\in \\mathbb{Z}^+ $, with $ 1 \\le l \\le r \\le 10^9 $, $ 1 \\le x \\le y \\le 10^9 $.\n\nDefine the set:\n\n$$\n\\mathcal{P} = \\left\\{ (a, b) \\in \\mathbb{Z}^2 \\,\\middle|\\, l \\le a, b \\le r,\\ \\gcd(a, b) = x,\\ \\mathrm{lcm}(a, b) = y \\right\\}\n$$\n\nThen:\n\n- If $ x \\nmid y $, then $ |\\mathcal{P}| = 0 $.\n- Else, let $ k = \\frac{y}{x} $, and factor $ k = \\prod_{i=1}^m p_i^{e_i} $ into distinct prime powers.\n- For each subset $ S \\subseteq \\{1, \\dots, m\\} $, define:\n  $$\n  a_S = x \\cdot \\prod_{i \\in S} p_i^{e_i}, \\quad b_S = x \\cdot \\prod_{i \\notin S} p_i^{e_i}\n  $$\n- Then:\n  $$\n  |\\mathcal{P}| = \\left| \\left\\{ S \\subseteq \\{1, \\dots, m\\} \\,\\middle|\\, l \\le a_S \\le r \\text{ and } l \\le b_S \\le r \\right\\} \\right|\n  $$\n\n**Output**: $ |\\mathcal{P}| $\n\n---\n\nNote: Since $ m = \\omega(k) \\le \\log_2(k) \\le \\log_2(10^9) < 30 $, iterating over all $ 2^m $ subsets is feasible.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF992B","tags":["math","number theory"],"sample_group":[["1 2 1 2","2"],["1 12 1 12","4"],["50 100 3 30","0"]],"created_at":"2026-03-03 11:00:39"}}