Codeforces 第 976 轮（第 2 分部 ABCDE 问题）视频解析

A. Find Minimum Operations

Problem Statement

You are given two integers $n$ and $k$.

In one operation, you can subtract any power of $k$ from $n$. Formally, in one operation, you can replace $n$ by $(n-k^x)$ for any non-negative integer $x$.

Find the minimum number of operations required to make $n$ equal to $0$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The only line of each test case contains two integers $n$ and $k$ ($1\le n,k\le 10^9$).

Output

For each test case, output the minimum number of operations on a new line.

Example

input
6
5 2
3 5
16 4
100 3
6492 10
10 1

output
2
3
1
4
21
10

Note

In the first test case, you can choose $a=1$, $b=2$, $c=3$ in the only operation, since $\gcd (1,2)=\gcd (2,3)=\gcd (1,3)=1$, and then there are no more integers in the set, so no more operations can be performed.

In the second test case, you can choose $a=3$, $b=5$, $c=7$ in the only operation.

In the third test case, you can choose $a=11$, $b=19$, $c=20$ in the first operation, $a=13$, $b=14$, $c=15$ in the second operation, and $a=10$, $b=17$, $c=21$ in the third operation. After the three operations, the set $s$ contains the following integers: $12$, $16$, $18$. It can be proven that it’s impossible to perform more than $3$ operations.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

void solve() {
	int n, k;
	cin >> n >> k;
	
	if (k == 1) {
		cout << n << endl;
		return;
	}
	int cnt = 0, s = n, mul = 1, res = 0;
	while (s) s /= k, cnt ++, mul *= k;
	for (int i = cnt; i >= 0; i --)
		res += n / mul, n %= mul, mul /= k;
	
	cout << res << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int dt;
    cin >> dt;
    while (dt -- ) solve();

	return 0;
}

---

B. Brightness Begins

Problem Statement

Imagine you have $n$ light bulbs numbered $1,2,\dots ,n$. Initially, all bulbs are on. To flip the state of a bulb means to turn it off if it used to be on, and to turn it on otherwise.

Next, you do the following:

• for each $i=1,2,\dots ,n$, flip the state of all bulbs $j$ such that $j$ is divisible by $i^{†}$.

After performing all operations, there will be several bulbs that are still on. Your goal is to make this number exactly $k$.

Find the smallest suitable $n$ such that after performing the operations there will be exactly $k$ bulbs on. We can show that an answer always exists.

${}^{†}$ An integer $x$ is divisible by $y$ if there exists an integer $z$ such that $x=y\cdot z$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The only line of each test case contains a single integer $k$ ($1\le k\le 10^{18}$).

Output

For each test case, output $n$ — the minimum number of bulbs.

Example

input
3
1
3
8

output
2
5
11

Note

In the first test case, the minimum number of bulbs is $2$. Let’s denote the state of all bulbs with an array, where $1$ corresponds to a turned on bulb, and $0$ corresponds to a turned off bulb. Initially, the array is $[1,1]$.

• After performing the operation with $i=1$, the array becomes $[\underline{0},\underline{0}]$.
• After performing the operation with $i=2$, the array becomes $[0,\underline{1}]$.

In the end, there are $k=1$ bulbs on. We can also show that the answer cannot be less than $2$.

In the second test case, the minimum number of bulbs is $5$. Initially, the array is $[1,1,1,1,1]$.

• After performing the operation with $i=1$, the array becomes $[\underline{0},\underline{0},\underline{0},\underline{0},\underline{0}]$.
• After performing the operation with $i=2$, the array becomes $[0,\underline{1},0,\underline{1},0]$.
• After performing the operation with $i=3$, the array becomes $[0,1,\underline{1},1,0]$.
• After performing the operation with $i=4$, the array becomes

  上一篇： [论文解读】ECCV2018 精细分类：自监督机制NTS-Net模型引领新方向（附论文地址）

  下一篇： 关系数据库与非关系数据库的区别