← 返回题目列表

Codeforces · 1350/A

A. Orac 和因素

中文机器翻译题面 查看原题

Orac正在研究数论,他对除数的性质感兴趣。

对于两个正整数 $$$a$$$ 和 $$$b$$$,当且仅当存在整数 $$$c$$$ 时,$$$a$$$ 是 $$$b$$$ 的约数,使得 $$$a\cdot c=b$$$。

对于 $$$n \ge 2$$$,我们将 $$$f(n)$$$ 表示 $$$n$$$ 的最小正除数,$$$1$$$ 除外。

例如,$$$f(7)=7,f(10)=2,f(35)=5$$$。

对于固定整数 $$$n$$$,Orac 决定将 $$$f(n)$$$ 添加到 $$$n$$$ 中。

例如,如果他有一个整数$$$n=5$$$,则$$$n$$$的新值将等于$$$10$$$。如果他有一个整数$$$n=6$$$,则$$$n$$$将更改为$$$8$$$。

Orac非常喜欢它,所以他决定重复这个操作几次。

现在,对于两个正整数$$$n$$$和$$$k$$$,Orac要求你将$$$f(n)$$$添加到$$$n$$$恰好$$$k$$$次(注意$$$n$$$在每次操作后都会改变,所以$$$f(n)$$$也可能改变)并告诉他$$$n$$$的最终值。

例如,如果Orac给你$$$n=5$$$和$$$k=2$$$,首先你应该添加$$$f(5)=5$$$到$$$n=5$$$,这样你的$$$n$$$的新值将等于$$$n=10$$$,之后,你应该添加$$$f(10)=2$$$到$$$10$$$,因此 $$$n$$$ 的新(也是最终!)值将等于 $$$12$$$。

Orac 可能会多次询问您这些问题。

输入

输入的第一行是一个整数 $$$t\ (1\le t\le 100)$$$:Orac 询问你的次数。

接下来的$$$t$$$行包含两个正整数$$$n,k\ (2\le n\le 10^6, 1\le k\le 10^9)$$$,对应于Orac的查询。

保证$$$n$$$的总和最多为$$$10^6$$$。

输出

打印 $$$t$$$ 行,其中第 $$$i$$$ 行应包含 Orac 第 $$$i$$$ 查询中 $$$n$$$ 的最终值。

示例

输入 #1

3
5 1
8 2
3 4

输出 #1

10
12
12

注意

在第一个查询中,$$$n=5$$$ 和 $$$k=1$$$。 $$$5$$$的约数是$$$1$$$和$$$5$$$,除了$$$1$$$之外最小的一个是$$$5$$$。因此,唯一的操作是将$$$f(5)=5$$$ 与$$$5$$$ 相加,结果为$$$10$$$。

在第二个查询中,$$$n=8$$$ 和 $$$k=2$$$。 $$$8$$$的约数为$$$1,2,4,8$$$,其中除$$$1$$$外最小的为$$$2$$$,则$$$8$$$经过一次运算后变为$$$8+(f(8)=2)=10$$$。 $$$10$$$ 的约数为 $$$1,2,5,10$$$,其中除 $$$1$$$ 之外最小的为 $$$2$$$,因此答案为 $$$10+(f(10)=2)=12$$$。

在第三个查询中,$$$n$$$ 更改如下:$$$3 \to 6 \to 8 \to 10 \to 12$$$。