D. Modulo maths

Codeforces

IDCF10049D

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Birute loves modular arithmetics, but hates long problem statements. Given _n_, find _f(n)_. The first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are integer values of number _n_ (1 ≤ n ≤ 10007). For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the value of _f(n)_. _Fun fact: 1 is neither prime nor composite number._ ## Input The first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are integer values of number _n_ (1 ≤ n ≤ 10007). ## Output For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the value of _f(n)_. [samples] ## Note _Fun fact: 1 is neither prime nor composite number._

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ i \in \{1, \dots, T\} $, let $ N_i \in \mathbb{Z} $ denote the input integer, and define the set $ S_i = \{1, 2, \dots, N_i\} $. **Constraints** 1. $ 1 \le T \le 1000 $ 2. For each $ i \in \{1, \dots, T\} $, $ 1 \le N_i \le 10^6 $ **Objective** For each test case $ i $, find the maximum size $ p_i $ of a subset $ S_i' \subseteq S_i $ such that for all distinct $ a, b \in S_i' $, $ \gcd(a, b) = 1 $. Output $ p_i $ for each $ i $.

API Response (JSON)

{
  "problem": {
    "name": "D. Modulo maths",
    "description": {
      "content": "Birute loves modular arithmetics, but hates long problem statements. Given _n_, find _f(n)_. The first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are int",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10049D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Birute loves modular arithmetics, but hates long problem statements.\n\nGiven _n_, find _f(n)_.\n\nThe first line contains the number of test cases _T_ (T ≤ 50). In the following _T_ lines there are integ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $, let $ N_i \\in \\mathbb{Z} $ denote the input integer, and define the set $ S_i = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments