{"problem":{"name":"A6. Rasta-lover Pair","description":{"content":"A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that: px ≡ q (modn) Subtasks 1 - 3:  Given n, calculate the number o","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":15000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFA6"},"statements":[{"statement_type":"Markdown","content":"A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:\n\npx ≡ q (modn)\n\nSubtasks 1 - 3: \n\nGiven n, calculate the number of Rasta - lover pairs modulo 109 + 7.\n\nSubtasks 4 - 6:\n\nA positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes.\n\nFor a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists).\n\nIf M is equal to  for a given A, then you have to calculate M modulo 109 + 7.\n\nSubtasks:\n\nEach subtask consists of one testcase.\n\nInput consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.\n\nPrint the answer modulo 109 + 7 in one line.\n\n## Input\n\nEach subtask consists of one testcase.Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A.\n\n## Output\n\nPrint the answer modulo 109 + 7 in one line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一对整数 #cf_span[(p, q)] 被称为 #cf_span[Rasta - lover]，当且仅当 #cf_span[1 ≤ p, q < n] 且存在一个正整数 #cf_span[x] 使得：\n\n#cf_span[px ≡ q] #cf_span[(modn)]\n\n子任务 #cf_span[1 - 3]：\n\n给定 #cf_span[n]，计算 #cf_span[Rasta - lover] 对的数量，对 #cf_span[109 + 7] 取模。\n\n子任务 #cf_span[4 - 6]：\n\n一个正整数 #cf_span[p] 被称为 #cf_span[n - Rastaly]，当且仅当 #cf_span[p < n] 且存在一个正整数 #cf_span[x] 使得 #cf_span[px ≡ 1] #cf_span[(modn)]，且 #cf_span[p] 与 #cf_span[n] 互质。\n\n对于正整数 #cf_span[n]，#cf_span[f(n)] 是最小的正整数 #cf_span[a]，使得对每个 #cf_span[n - Rastaly] 数 #cf_span[p]，都有 #cf_span[pa ≡ 1] #cf_span[(modn)]（这个数总是存在）。\n\n如果给定 #cf_span[A] 时 #cf_span[M] 等于 ，则你需要计算 #cf_span[M] 对 #cf_span[109 + 7] 取模的结果。\n\n子任务：\n\n每个子任务包含一个测试用例。\n\n输入由一个数字组成。对于子任务 1-3，它是 #cf_span[n]；对于子任务 4-6，它是 #cf_span[A]。\n\n## Input\n\n每个子任务包含一个测试用例。输入由一个数字组成。对于子任务 1-3，它是 #cf_span[n]；对于子任务 4-6，它是 #cf_span[A]。\n\n## Output\n\n请在一行中输出对 #cf_span[109 + 7] 取模后的答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ n \\in \\mathbb{Z}^+ $.\n- Let $ \\mathbb{Z}_n^* = \\{ p \\in \\mathbb{Z} \\mid 1 \\leq p < n, \\gcd(p, n) = 1 \\} $ be the multiplicative group modulo $ n $.\n- Let $ \\lambda(n) $ denote the Carmichael function: the smallest positive integer $ a $ such that $ p^a \\equiv 1 \\pmod{n} $ for all $ p \\in \\mathbb{Z}_n^* $.\n\n---\n\n**Subtasks 1–3:**\n\nGiven $ n $, compute the number of pairs $ (p, q) \\in \\mathbb{Z}^2 $ such that:\n\n$$\n1 \\leq p, q < n \\quad \\text{and} \\quad \\exists x \\in \\mathbb{Z}^+ \\text{ such that } p^x \\equiv q \\pmod{n}.\n$$\n\nLet $ S(n) = \\left| \\left\\{ (p, q) \\in [1, n-1]^2 \\mid \\exists x \\in \\mathbb{Z}^+, p^x \\equiv q \\pmod{n} \\right\\} \\right| $.\n\nCompute $ S(n) \\mod (10^9 + 7) $.\n\n---\n\n**Subtasks 4–6:**\n\nGiven $ A $, compute $ \\lambda(A) \\mod (10^9 + 7) $, where $ \\lambda(A) $ is the Carmichael function of $ A $, defined as:\n\n$$\n\\lambda(A) = \\min \\left\\{ a \\in \\mathbb{Z}^+ \\mid \\forall p \\in \\mathbb{Z}_A^*, \\; p^a \\equiv 1 \\pmod{A} \\right\\}.\n$$\n\n(Note: The problem defines $ f(n) = \\lambda(n) $, and input is $ A $, so output is $ \\lambda(A) \\mod (10^9 + 7) $.)\n\n---\n\n**Final Output:**\n\nFor each test case, output:\n\n- $ S(n) \\mod (10^9 + 7) $, if input is $ n $ (subtasks 1–3),\n- $ \\lambda(A) \\mod (10^9 + 7) $, if input is $ A $ (subtasks 4–6).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFA6","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}