A. Taymyr is calling you

Codeforces

IDCF764A

Time1000ms

Memory255MB

Difficulty—

brute forceimplementationmath

English · Original

Chinese · Translation

Formal · Original

Comrade Dujikov is busy choosing artists for Timofey's birthday and is recieving calls from Taymyr from Ilia-alpinist. Ilia-alpinist calls every _n_ minutes, i.e. in minutes _n_, 2_n_, 3_n_ and so on. Artists come to the comrade every _m_ minutes, i.e. in minutes _m_, 2_m_, 3_m_ and so on. The day is _z_ minutes long, i.e. the day consists of minutes 1, 2, ..., _z_. How many artists should be killed so that there are no artists in the room when Ilia calls? Consider that a call and a talk with an artist take exactly one minute. ## Input The only string contains three integers — _n_, _m_ and _z_ (1 ≤ _n_, _m_, _z_ ≤ 104). ## Output Print single integer — the minimum number of artists that should be killed so that there are no artists in the room when Ilia calls. [samples] ## Note Taymyr is a place in the north of Russia. In the first test the artists come each minute, as well as the calls, so we need to kill all of them. In the second test we need to kill artists which come on the second and the fourth minutes. In the third test — only the artist which comes on the sixth minute.

Comrade Dujikov 正在为 Timofey 的生日挑选艺术家，并不断接到来自北方 Taymyr 地区的 Ilia-alpinist 的电话。 Ilia-alpinist 每隔 #cf_span[n] 分钟打一次电话，即在第 #cf_span[n]、#cf_span[2n]、#cf_span[3n] 分钟等时刻来电。艺术家则每 #cf_span[m] 分钟到来一次，即在第 #cf_span[m]、#cf_span[2m]、#cf_span[3m] 分钟等时刻到达。一天共持续 #cf_span[z] 分钟，即从第 #cf_span[1] 到第 #cf_span[z] 分钟。为了确保 Ilia 打电话时房间里没有艺术家，至少需要杀死多少名艺术家？假设每次通话和与艺术家的交谈都恰好持续一分钟。输入仅包含一行，三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[z]（#cf_span[1 ≤ n, m, z ≤ 10^4]）。请输出一个整数——为确保 Ilia 打电话时房间内无艺术家，所需杀死的最少艺术家数量。 Taymyr 是俄罗斯北部的一个地方。在第一个测试用例中，艺术家每分钟都来，而电话也每分钟打来，因此我们需要杀死所有艺术家。在第二个测试用例中，我们需要杀死在第 2 分钟和第 4 分钟到达的艺术家。在第三个测试用例中，只需杀死在第 6 分钟到达的那一位艺术家。 ## Input 输入仅包含一行，三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[z]（#cf_span[1 ≤ n, m, z ≤ 10^4]）。 ## Output 请输出一个整数——为确保 Ilia 打电话时房间内无艺术家，所需杀死的最少艺术家数量。 [samples] ## Note Taymyr 是俄罗斯北部的一个地方。在第一个测试用例中，艺术家每分钟都来，而电话也每分钟打来，因此我们需要杀死所有艺术家。在第二个测试用例中，我们需要杀死在第 2 分钟和第 4 分钟到达的艺术家。在第三个测试用例中，只需杀死在第 6 分钟到达的那一位艺术家。

**Definitions** Let $ n, m, z \in \mathbb{Z}^+ $ with $ 1 \leq n, m, z \leq 10^4 $. Let $ I = \{ kn \mid k \in \mathbb{Z}^+, kn \leq z \} $ be the set of minutes when Ilia calls. Let $ A = \{ lm \mid l \in \mathbb{Z}^+, lm \leq z \} $ be the set of minutes when artists arrive. Each event (call or artist arrival) occupies exactly one minute. **Constraints** - $ I \subseteq \{1, 2, \dots, z\} $ - $ A \subseteq \{1, 2, \dots, z\} $ **Objective** Find the size of the intersection: $$ |I \cap A| $$ This is the minimum number of artists that must be killed to ensure no artist is present during a call.

Samples

Input #1

1 1 10

Output #1

Input #2

1 2 5

Output #2

Input #3

2 3 9

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Taymyr is calling you",
    "description": {
      "content": "Comrade Dujikov is busy choosing artists for Timofey's birthday and is recieving calls from Taymyr from Ilia-alpinist. Ilia-alpinist calls every _n_ minutes, i.e. in minutes _n_, 2_n_, 3_n_ and so on",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 261120
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF764A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Comrade Dujikov is busy choosing artists for Timofey's birthday and is recieving calls from Taymyr from Ilia-alpinist.\n\nIlia-alpinist calls every _n_ minutes, i.e. in minutes _n_, 2_n_, 3_n_ and so on...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Comrade Dujikov 正在为 Timofey 的生日挑选艺术家，并不断接到来自北方 Taymyr 地区的 Ilia-alpinist 的电话。\n\nIlia-alpinist 每隔 #cf_span[n] 分钟打一次电话，即在第 #cf_span[n]、#cf_span[2n]、#cf_span[3n] 分钟等时刻来电。艺术家则每 #cf_span[m] 分钟到来一次，即在第 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, z \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m, z \\leq 10^4 $.  \n\nLet $ I = \\{ kn \\mid k \\in \\mathbb{Z}^+, kn \\leq z \\} $ be the set of minutes when Ilia calls.  \nLet $ A = \\{ l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments