B. Riana and the Blind Date

Codeforces

IDCF10255B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Last valentines, Riana went on a blind date with Zanoki-kun, a famous _shoujo manga mangaka_, but after a series of misunderstandings, she accidentally became one of his _manga_ assistants. In his new manga, _Biidoru wa Meido-sama!_ (_Class Beadle is Maid!_), he adopts a new system of expressing dates on a calendar. In this system, Zanoki-kun takes the numerical value of the month (January = $1$, February = $2$, March = $6$, ... , November = $11$, December = $12$), and appends the day to it. Thus, representing each date as a single integer. For example: January $1$ becomes $11$. February $23$ becomes $223$. November $5$ becomes $115$. December $24$ becomes $1224$. It just so happens that it takes Zanoki-kun $1$ pencil to draw the integer '$1$', $2$ pencils to draw the integer '$2$', and so on. Generally, it takes Zanoki-kun $n$ pencils to draw the integer '$n$'. In chapter $1$ of _Biidoru wa Meido-sama!_, Zanoki-kun decides to draw all the dates from year *$A$* to year *$B$* inclusive. Zanoki-kun wants to prepare all the pencils he needs before he starts drawing, but he doesn't want to waste any more money than he has to, so he commissions his _manga_ assistants, including Riana, to compute the least number of pencils he needs to draw all the dates from year *$A$* to year *$B$* inclusive. Note that the date does not include the year. More formally, let *$S$* be the least number of pencils Zanoki-kun needs in order to draw all the dates from year *$A$* and year *$B$* inclusive. Find *$S$* given *$A$* and *$B$*. Note that three criteria must be taken into account to identify leap years: Two spaced integers *$A$* and *$B$*. The first integer, *$A$*, is the year that Zanoki-kun chooses to begin drawing at. The second integer, *$B$*, is the year that Zanoki-kun chooses to end drawing at. It is guaranteed that *$A$* and *$B$* ranges from $0$ to $10^(18)$ inclusive. ($0 <= A <= B <= 10^(18)$) Output the least number of pencils Zanoki-kun needs in order to draw all the dates from year *$A$* and year *$B$* inclusive. Since the answer can get quite large, output only the positive remainder when *$S$* is divided by $104206969$, Zanoki-kun's favorite a prime number. $11 + 12 + \\dots + 21 + 22 + \\dots + 31 + 32 + \\dots + 41 + 42 + \\dots + 51 + 52 + \\dots + 61 + 62 + \\dots$ $+ 71 + 72 + \\dots + 81 + 82 + \\dots + 91 + 92 + \\dots + 101 + 102 + \\dots + 111 + 112 + \\dots$ $+ 121 + 122 + \\dots + 11 + 12 + \\dots + 21 + 22 + \\dots + 31 + 32 + \\dots + 41 + 42 + \\dots + 51 + 52 + \\dots$ $+ 61 + 62 + \\dots + 71 + 72 + \\dots + 81 + 82 + \\dots + 91 + 92 + \\dots + 101 + 102 + \\dots + 111 + 112 + \\dots$ $+ 121 + 122 + \\dots + 11 + 12 + \\dots + 21 + 22 + \\dots + 31 + 32 + \\dots + 41 + 42 + \\dots + 51 + 52 + \\dots$ $+ 61 + 62 + \\dots + 71 + 72 + \\dots + 81 + 82 + \\dots + 91 + 92 + \\dots + 101 + 102 + \\dots$ $+ 111 + 112 + \\dots + 121 + 122 + \\dots + 1230 + 1231 = 542274$ ## Input Two spaced integers *$A$* and *$B$*. The first integer, *$A$*, is the year that Zanoki-kun chooses to begin drawing at. The second integer, *$B$*, is the year that Zanoki-kun chooses to end drawing at.It is guaranteed that *$A$* and *$B$* ranges from $0$ to $10^(18)$ inclusive. ($0 <= A <= B <= 10^(18)$) ## Output Output the least number of pencils Zanoki-kun needs in order to draw all the dates from year *$A$* and year *$B$* inclusive. Since the answer can get quite large, output only the positive remainder when *$S$* is divided by $104206969$, Zanoki-kun's favorite a prime number. [samples] ## Note $11 + 12 + \\dots + 21 + 22 + \\dots + 31 + 32 + \\dots + 41 + 42 + \\dots + 51 + 52 + \\dots + 61 + 62 + \\dots$ $+ 71 + 72 + \\dots + 81 + 82 + \\dots + 91 + 92 + \\dots + 101 + 102 + \\dots + 111 + 112 + \\dots$ $+ 121 + 122 + \\dots + 11 + 12 + \\dots + 21 + 22 + \\dots + 31 + 32 + \\dots + 41 + 42 + \\dots + 51 + 52 + \\dots$ $+ 61 + 62 + \\dots + 71 + 72 + \\dots + 81 + 82 + \\dots + 91 + 92 + \\dots + 101 + 102 + \\dots + 111 + 112 + \\dots$ $+ 121 + 122 + \\dots + 11 + 12 + \\dots + 21 + 22 + \\dots + 31 + 32 + \\dots + 41 + 42 + \\dots + 51 + 52 + \\dots$ $+ 61 + 62 + \\dots + 71 + 72 + \\dots + 81 + 82 + \\dots + 91 + 92 + \\dots + 101 + 102 + \\dots$ $+ 111 + 112 + \\dots + 121 + 122 + \\dots + 1230 + 1231 = 542274$

**Definitions** Let $ x, y \in \mathbb{Z}^+ $ be given such that $ 1 \le x \le y \le 10^{12} $. Let $ (p, q) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ be a *private key*. The corresponding *public key* is $ (\gcd(p, q), \operatorname{lcm}(p, q)) $. **Constraints** Given public key: $ \gcd(p, q) = x $, $ \operatorname{lcm}(p, q) = y $. **Objective** Count the number of ordered pairs $ (p, q) $ such that: $$ \gcd(p, q) = x \quad \text{and} \quad \operatorname{lcm}(p, q) = y $$

API Response (JSON)

{
  "problem": {
    "name": "B. Riana and the Blind Date",
    "description": {
      "content": "Last valentines, Riana went on a blind date with Zanoki-kun, a famous _shoujo manga mangaka_, but after a series of misunderstandings, she accidentally became one of his _manga_ assistants.  In his n",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10255B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Last valentines, Riana went on a blind date with Zanoki-kun, a famous _shoujo manga mangaka_, but after a series of misunderstandings, she accidentally became one of his _manga_ assistants. \n\nIn his n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ x, y \\in \\mathbb{Z}^+ $ be given such that $ 1 \\le x \\le y \\le 10^{12} $.  \nLet $ (p, q) \\in \\mathbb{Z}^+ \\times \\mathbb{Z}^+ $ be a *private key*.  \nThe corresponding *public ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments