题目描述:
在你们的帮助下,TT 轻松地完成了上一个神秘任务。
但是令人没有想到的是,几天后,TT 再次遇到了那个神秘人。
而这一次,神秘人决定加大难度,并许诺 TT,如果能够完成便给他一个奖励。
任务依旧只给了两个数字,分别表示 n 和 k,不过这一次是要求 TT 给出无法被 n 整除的第 k 大的正整数。
例如 n = 3,k = 7,则前 7 个无法被 n 整除的正整数为 [1 2 4 5 7 8 10],答案为 10。
好奇的 TT 想要知道奖励究竟是什么,你能帮帮他吗?
Input
第一行一个整数 T,表示数据组数,不超过 1000。
之后 T 行,每一行给出两个正整数,分别表示 n(2 ≤ n ≤ 1e9)、k(1 ≤ k ≤ 1e9)。
Output
对于每一组数据,输出无法被 n 整除的第 k 大的正整数。
Example
Input
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1
Output
10
15
1999999999
113
1000000001
1
题目分析:
这个题和上一个题一样,如果数据范围小的话可以很容易的一个一个试出来,但是这个数据范围太大了,直接导致本地测试的时候就需要好几秒,提交到OJ上直接TLE,所以本题还是得要巧劲。
如果数据类型小的话,那么本题的解法就是用一个变量i一个一个加,如果i是n的倍数那就跳过去,否则i++,直到第k个数为止,然后就可以输出了,这个题和CCFCSP的19年第一个题比较像,但是那个题的数据范围很小,这里就到了1e9,所以不能一个一个列举,我们只能用公式。
如果n>k,那么没有整除的数,直接就是k。
if(k<n)
{
cout<<k<<endl;
}
其他情况就有整除的数了,我们用余数来分析一下,那么余数的序列一定是1,2,3,4…n-1,0,1,2,3,4…,n-1,0…这样我们就能看出来,除去0之后就是1到n-1的一个循环,可以把每n-1个数设置为一组。还有要注意第一组是没有0开头的,所以求组数的时候要把第一个0去掉,也就是剩余k-1个数里面有几组,那就是(k-1)/(n-1)组,这样加上原来的k就是加上倍数之后有多少个数了。
cout<<k+(k-1)/(n-1)<<endl;
代码如下:
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
if(k<n)
{
cout<<k<<endl;
}
else
{
cout<<k+(k-1)/(n-1)<<endl;
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)