[SDCPC 2023] Math Problem

Luogu

IDLGP9560

Time4000ms

Memory1024MB

DifficultyP4

数学2023山东O2优化省赛/邀请赛

Given two positive integers $n$ and $k$, you can perform the following two types of operations any number of times (including zero times): - Choose an integer $x$ which satisfies $0 \leq x < k$, and change $n$ into $k\cdot n+x$. It will cost you $a$ coins to perform this operation once. The integer $x$ you choose each time can be different. - Change $n$ into $\lfloor \frac{n}{k} \rfloor$. It will cost you $b$ coins to perform this operation once. Note that $\lfloor \frac{n}{k} \rfloor$ is the largest integer which is less than or equal to $\frac{n}{k}$. Given a positive integer $m$, calculate the minimum number of coins needed to change $n$ into a multiple of $m$. Please note that $0$ is a multiple of any positive integer. ## Input There are multiple test cases. The first line of the input contains an integer $T$ ($1\leq T\leq 10^5$) indicating the number of test cases. For each test case: The first line contains five integers $n$, $k$, $m$, $a$, $b$ ($1\leq n\leq 10^{18}$, $1\leq k, m, a, b\leq 10^9$). ## Output For each test case output one line containing one integer, indicating the minimum number of coins needed to change $n$ into a multiple of $m$. If this goal cannot be achieved, output $-1$ instead. [samples] ## Note For the first sample test case, initially $n=101$. The optimal steps are shown as follows: - Firstly, perform the second type of operation once. Change $n$ into $\lfloor \frac{n}{4} \rfloor=25$. This step costs $5$ coins. - Then, perform the first type of operation once. Choose $x = 3$ and change $n$ into $4\cdot n+3=103$. This step costs $3$ coins. - Then, perform the first type of operation once. Choose $x = 2$ and change $n$ into $4\cdot n+2=414$. This step costs $3$ coins. - As $414=2 \times 207$, $n$ is a multiple of $m$. The total cost is $5+3+3=11$ coins. For the second sample test case, perform the second type of operation twice will change $n$ into $0$. The total cost is $1 + 1 = 2$ coins. For the third sample test case, as $n = 114 = 6 \times 19$ is already a multiple of $m$, no operation is needed. The total cost is $0$ coins.

Samples

Input #1

4
101 4 207 3 5
8 3 16 100 1
114 514 19 19 810
1 1 3 1 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[SDCPC 2023] Math Problem",
    "description": {
      "content": "Given two positive integers $n$ and $k$, you can perform the following two types of operations any number of times (including zero times): - Choose an integer $x$ which satisfies $0 \\leq x < k$, and ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9560"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given two positive integers $n$ and $k$, you can perform the following two types of operations any number of times (including zero times):\n\n- Choose an integer $x$ which satisfies $0 \\leq x < k$, and ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments