{"problem":{"name":"096. Numbers","description":{"content":"Numbers You're working with large numbers, and you want to calculate the totient function of a certain one. The totient function of a number $n$ is defined as the number of positive integers less tha","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269096"},"statements":[{"statement_type":"Markdown","content":"Numbers\n\nYou're working with large numbers, and you want to calculate the totient function of a certain one. The totient function of a number $n$ is defined as the number of positive integers less than or equal $n$ that are relatively prime with $n$, i.e. the number of integers $k$ such that $k$ <= $n$ and $g c d (k, n) = 1$.\n\nFor example, the totient of $15$ is $8$, because 1, 2, 4, 7, 8, 11, 13, and 14 are relatively prime with $15$, while 3, 5, 6, 9, 10, 12, and 15 are not. 4 is relatively prime with 15, because there aren't any common factors of 4 and 15. 4 has factors {2}, and 15 has factors {3, 5}. On the other hand, 10 is not relatively prime with 15, because 10 and 15 both have a common factor of 5.\n\nGiven an integer $n$, figure out the value of $φ (n)$, where $φ$ represents the totient function as described above.\n\nThe only line of input contains a single positive integer $n$ less than 1000.\n\nOutput a single positive integer $p$: the value of $φ (n)$ as described above.\n\n## Input\n\nThe only line of input contains a single positive integer $n$ less than 1000.\n\n## Output\n\nOutput a single positive integer $p$: the value of $φ (n)$ as described above.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ n < 1000 $.  \nLet $ \\varphi(n) $ denote Euler’s totient function: the count of integers $ k \\in \\{1, 2, \\dots, n\\} $ such that $ \\gcd(k, n) = 1 $.\n\n**Constraints**  \n$ 1 \\leq n < 1000 $\n\n**Objective**  \nCompute:  \n$$\n\\varphi(n) = \\left| \\left\\{ k \\in \\mathbb{Z} \\mid 1 \\leq k \\leq n \\text{ and } \\gcd(k, n) = 1 \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269096","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}