E. Lostborn

Codeforces

IDCF93E

Time2000ms

Memory256MB

Difficulty—

dpmathnumber theory

English · Original

Chinese · Translation

Formal · Original

Igor K. very much likes a multiplayer role playing game WineAge II. Who knows, perhaps, that might be the reason for his poor performance at the university. As any person who plays the game, he is interested in equipping his hero with as good weapon and outfit as possible. One day, as he was reading the game's forum yet again, he discovered a very interesting fact. As it turns out, each weapon in the game is characterised with _k_ different numbers: _a_1, ..., _a__k_. They are called hit indicators and according to the game developers' plan they are pairwise coprime. The damage that is inflicted during a hit depends not only on the weapon's characteristics, but also on the hero's strength parameter. Thus, if the hero's strength equals _n_, than the inflicted damage will be calculated as the number of numbers on the segment , that aren't divisible by any hit indicator _a__i_. Recently, having fulfilled another quest, Igor K. found a new Lostborn sword. He wants to know how much damage he will inflict upon his enemies if he uses it. ## Input The first line contains two integers: _n_ and _k_ (1 ≤ _n_ ≤ 1013, 1 ≤ _k_ ≤ 100). They are the indicator of Igor K's hero's strength and the number of hit indicators. The next line contains space-separated _k_ integers _a__i_ (1 ≤ _a__i_ ≤ 1000). They are Lostborn sword's hit indicators. The given _k_ numbers are pairwise coprime. ## Output Print the single number — the damage that will be inflicted by Igor K.'s hero when he uses his new weapon. **Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator**. [samples]

Igor K. 非常喜欢一款多人在线角色扮演游戏 WineAge II。也许正是这个原因，导致他在大学的表现不佳。和所有玩这款游戏的人一样，他热衷于为自己的角色配备尽可能优秀的武器和装备。一天，当他再次阅读游戏论坛时，他发现了一个非常有趣的事实。原来，游戏中的每件武器都由 #cf_span[k] 个不同的数字表征：#cf_span[a1, ..., ak]。这些数字被称为命中指标，根据游戏开发者的设定，它们两两互质。每次攻击造成的伤害不仅取决于武器的特性，还取决于英雄的力量值。因此，如果英雄的力量值为 #cf_span[n]，则造成的伤害将等于区间内不被任何命中指标 #cf_span[ai] 整除的整数个数。最近，完成另一个任务后，Igor K. 找到了一把新的 Lostborn 剑。他想知道使用这把剑时，自己能对敌人造成多少伤害。第一行包含两个整数：#cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 1013]，#cf_span[1 ≤ k ≤ 100]），分别表示 Igor K. 英雄的力量值和命中指标的数量。第二行包含 #cf_span[k] 个用空格分隔的整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 1000]），表示 Lostborn 剑的命中指标。给定的 #cf_span[k] 个数两两互质。请输出一个整数——Igor K. 的英雄使用新武器时所造成的伤害。 *请注意，在 C++ 中请勿使用 %lld 特定格式符读写 64 位整数。建议使用 cin、cout 流，或 %I64d 特定格式符。* ## Input 第一行包含两个整数：#cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 1013]，#cf_span[1 ≤ k ≤ 100]），分别表示 Igor K. 英雄的力量值和命中指标的数量。第二行包含 #cf_span[k] 个用空格分隔的整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 1000]），表示 Lostborn 剑的命中指标。给定的 #cf_span[k] 个数两两互质。 ## Output 请输出一个整数——Igor K. 的英雄使用新武器时所造成的伤害。*请注意，在 C++ 中请勿使用 %lld 特定格式符读写 64 位整数。建议使用 cin、cout 流，或 %I64d 特定格式符。* [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the hero's strength. Let $ k \in \mathbb{Z}^+ $ be the number of hit indicators. Let $ A = \{a_1, a_2, \dots, a_k\} $ be a set of pairwise coprime positive integers with $ a_i \leq 1000 $. **Constraints** 1. $ 1 \leq n \leq 10^{13} $ 2. $ 1 \leq k \leq 100 $ 3. $ 1 \leq a_i \leq 1000 $ for all $ i \in \{1, \dots, k\} $ 4. $ \gcd(a_i, a_j) = 1 $ for all $ i \neq j $ **Objective** Compute the number of integers in the range $ [1, n] $ that are **not divisible** by any $ a_i \in A $: $$ \left| \left\{ x \in \mathbb{Z} \mid 1 \leq x \leq n,\ \forall i \in \{1,\dots,k\},\ a_i \nmid x \right\} \right| $$ Equivalently, using inclusion-exclusion: $$ n - \sum_{\emptyset \neq S \subseteq \{1,\dots,k\}} (-1)^{|S|-1} \left\lfloor \frac{n}{\prod_{i \in S} a_i} \right\rfloor $$

Samples

Input #1

20 3
2 3 5

Output #1

Input #2

50 2
15 8

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Lostborn",
    "description": {
      "content": "Igor K. very much likes a multiplayer role playing game WineAge II. Who knows, perhaps, that might be the reason for his poor performance at the university. As any person who plays the game, he is 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": "CF93E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Igor K. very much likes a multiplayer role playing game WineAge II. Who knows, perhaps, that might be the reason for his poor performance at the university. As any person who plays the game, he is int...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Igor K. 非常喜欢一款多人在线角色扮演游戏 WineAge II。也许正是这个原因，导致他在大学的表现不佳。和所有玩这款游戏的人一样，他热衷于为自己的角色配备尽可能优秀的武器和装备。\n\n一天，当他再次阅读游戏论坛时，他发现了一个非常有趣的事实。原来，游戏中的每件武器都由 #cf_span[k] 个不同的数字表征：#cf_span[a1, ..., ak]。这些数字被称为命中指标，根据游戏开发...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the hero's strength.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of hit indicators.  \nLet $ A = \\{a_1, a_2, \\dots, a_k\\} $ be a set of pairwise coprime p...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments