{"problem":{"name":"I. Distance","description":{"content":"Moon has learned the Hasse Diagram in his math course. Therefore, he draws an undirected graph with $n$ nodes indexed $1, 2, \\\\\\\\cdots, n$ and adds some edges between node $x$ and node $y$ if $x | y$ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFI"},"statements":[{"statement_type":"Markdown","content":"Moon has learned the Hasse Diagram in his math course. Therefore, he draws an undirected graph with $n$ nodes indexed $1, 2, \\\\\\\\cdots, n$ and adds some edges between node $x$ and node $y$ if $x | y$ and $frac(y, x)$ is a prime while the weight of the edge is $frac(y, x)$.\n\nMoon wants to know the value of $sum_{i = 1}^n sum_{j = 1}^n d i s (i, j)$, where $d i s (x, y)$ means the shortest distance between node $x$ and node $y$. Since the answer will be very large, you should print the answer modulo $10^9 + 7$.\n\nThe only line contains an integer $n$. ($1 <= n <= 10^(11)$)\n\nThe only line contains an integer, indicating the answer modulo $10^9 + 7$.\n\n$A | B$ means $A$ is one factor of $B$.\n\n## Input\n\nThe only line contains an integer $n$. ($1 <= n <= 10^(11)$)\n\n## Output\n\nThe only line contains an integer, indicating the answer modulo $10^9 + 7$.\n\n[samples]\n\n## Note\n\n$A | B$ means $A$ is one factor of $B$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"除了关于照明的投诉外，最近贝托恩市市政厅还收到了大量关于无线电信号覆盖不足的投诉。市长收到了 n 封投诉，它们都惊人地相似：在第 i 封投诉中，一位无线电爱好者提到，两家电台 x_i 和 y_i 的信号无法覆盖城市的一些区域，并要求至少其中一家电台的信号能够覆盖整个城市。\n\n当然，贝托恩市长目前正在努力满足这些投诉。一座新的无线电塔已在贝托恩安装，它可以以 1 到 M 之间的任意整数功率发射信号（记信号功率为 f）。市长决定选择一组电台，并与每个被选中的电台签订合同。要与第 i 家电台签订合同，必须满足以下条件：\n\n所有这些信息已经足以让市长意识到选择电台非常困难。但经过与专家咨询后，他了解到某些电台的信号可能会相互干扰：存在 m 对电台 (u_i, v_i) 使用相同的信号频率，对于每一对这样的电台，不可能同时与两家签订合同。*如果电台 x 和 y 使用相同的频率，且 y 和 z 使用相同的频率，并不意味着 x 和 z 使用相同的频率*。\n\n市长发现分析这种情况非常困难，因此聘请了你来帮助他。你需要选择一个信号功率 f 和一组电台来签订合同，使得：\n\n第一行包含 4 个整数 n, p, M 和 m（2 \\leq n, p, M, m \\leq 4 \\cdot 10^5）——投诉数量、电台数量、最大信号功率和干扰对数量。\n\n接下来 n 行描述投诉。每行包含两个整数 x_i 和 y_i（1 \\leq x_i < y_i \\leq p）——第 i 封投诉中提到的电台编号。*所有投诉互不相同*。\n\n接下来 p 行描述电台。每行包含两个整数 l_i 和 r_i（1 \\leq l_i \\leq r_i \\leq M）——如果城市与第 i 家电台签订合同，其信号功率必须满足的约束条件。\n\n接下来 m 行描述干扰电台对。每行包含两个整数 u_i 和 v_i（1 \\leq u_i < v_i \\leq p）——干扰电台的编号。*所有这些对互不相同*。\n\n如果无法选择信号功率和一组电台以满足所有条件，请输出 -1。\n\n否则，第一行输出两个整数 k 和 f —— 所选电台的数量和选定的信号功率。第二行输出 k 个从 1 到 p 的互不相同的整数 —— 要签订合同的电台编号（顺序任意）。如果有多个答案，输出任意一个即可；你无需最小化或最大化所选电台数量，信号功率同理。\n\n## Input\n\n第一行包含 4 个整数 n, p, M 和 m（2 \\leq n, p, M, m \\leq 4 \\cdot 10^5）——投诉数量、电台数量、最大信号功率和干扰对数量。接下来 n 行描述投诉。每行包含两个整数 x_i 和 y_i（1 \\leq x_i < y_i \\leq p）——第 i 封投诉中提到的电台编号。*所有投诉互不相同*。接下来 p 行描述电台。每行包含两个整数 l_i 和 r_i（1 \\leq l_i \\leq r_i \\leq M）——如果城市与第 i 家电台签订合同，其信号功率必须满足的约束条件。接下来 m 行描述干扰电台对。每行包含两个整数 u_i 和 v_i（1 \\leq u_i < v_i \\leq p）——干扰电台的编号。*所有这些对互不相同*。\n\n## Output\n\n如果无法选择信号功率和一组电台以满足所有条件，请输出 -1。否则，第一行输出两个整数 k 和 f —— 所选电台的数量和选定的信号功率。第二行输出 k 个从 1 到 p 的互不相同的整数 —— 要签订合同的电台编号（顺序任意）。如果有多个答案，输出任意一个即可；你无需最小化或最大化所选电台数量，信号功率同理。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ A, B, R \\in \\mathbb{Z}^+ $ with $ 1 \\leq A \\leq B \\leq 10^7 $ and $ R \\geq 1 $.\n\nLet $ X \\in \\mathbb{R} $ denote the radius of the red circle.\n\nThe configuration requires:  \n- One red circle of radius $ X $.  \n- An arbitrary number $ n \\geq 3 $ of yellow circles, each of radius $ R $, arranged in a closed chain such that:  \n  - Each yellow circle is externally tangent to two adjacent yellow circles.  \n  - Each yellow circle is externally tangent to the red circle.  \n  - No circle lies inside another.  \n\nThis forms a regular $ n $-gon of yellow circles centered around the red circle.  \nThe centers of the yellow circles lie on a circle of radius $ X + R $ centered at the red circle’s center.  \nThe distance between centers of two adjacent yellow circles is $ 2R $.  \n\nBy the law of cosines in the triangle formed by two adjacent yellow centers and the red center:  \n$$\n(2R)^2 = 2(X + R)^2 (1 - \\cos \\theta), \\quad \\text{where } \\theta = \\frac{2\\pi}{n}\n$$\n\nSolving:  \n$$\n4R^2 = 2(X + R)^2 \\left(1 - \\cos \\frac{2\\pi}{n}\\right)\n$$\n\n$$\n(X + R)^2 = \\frac{2R^2}{1 - \\cos \\frac{2\\pi}{n}}\n$$\n\n$$\nX = \\sqrt{ \\frac{2R^2}{1 - \\cos \\frac{2\\pi}{n}} } - R\n$$\n\nUsing identity $ 1 - \\cos \\theta = 2 \\sin^2(\\theta/2) $:  \n$$\nX = \\frac{R}{\\sin(\\pi/n)} - R = R \\left( \\frac{1}{\\sin(\\pi/n)} - 1 \\right)\n$$\n\nLet $ f(n) = R \\left( \\frac{1}{\\sin(\\pi/n)} - 1 \\right) $ for integers $ n \\geq 3 $.\n\nWe seek the number of distinct real values $ X = f(n) \\in [A, B] $ for $ n \\in \\mathbb{Z}, n \\geq 3 $.\n\nDefine:  \n$$\n\\mathcal{X} = \\left\\{ R \\left( \\frac{1}{\\sin(\\pi/n)} - 1 \\right) \\,\\middle|\\, n \\in \\mathbb{Z}, n \\geq 3, \\, A \\leq R \\left( \\frac{1}{\\sin(\\pi/n)} - 1 \\right) \\leq B \\right\\}\n$$\n\n**Objective:**  \nCompute $ |\\mathcal{X}| $, the number of distinct $ X \\in [A, B] $ achievable via integer $ n \\geq 3 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFI","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}