京东-优惠雷达
新人页面
精选商品
首月0月租体验,领12个月京东PLUS
自营热卖

#640(Div.4)C. K-th Not Divisible by n(数学)

夕阳牵手影成双 1年前   阅读数 105 0

题目描述

You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n.
For example, if n=3, and k=7, then all numbers that are not divisible by 3 are: 1,2,4,5,7,8,10,11,13…. The 7-th number among them is 10.

Input

The first line contains an integer t (1≤t≤1000) — the number of test cases in the input. Next, t test cases are given, one per line.
Each test case is two positive integers n (2≤n≤109) and k (1≤k≤109).

Output

For each test case print the k-th positive integer that is not divisible by n.

Example

input
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1
output
10
15
1999999999
113
1000000001
1

题目大意

给定两个数n、k,求第k个不能被n整除的数是多少。

题目分析

首先,我们来想想,从1开始的第k个数本来是k,但因为中间的某一些数不能取,所以答案为k+某个数。我们要求的就是这个数。
以第二组数据为例:
4 12
1,2,3|5,6,7|9,10,11|13,14,15
第12个数是15。前12个数有3个|,所以是12+3=15。所以这个数即为分割线的数量。

分割线的数量不好求,我们可以先求出组数:
因为每组有(n-1)个数,所以组数为k/(n-1)上取整,而分割线的数量即为组数-1,因此答案即为(k+n-1)/(n-1)-1。这个数可以简化为(k-1)/(n-1)

代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <set> 
#include <algorithm>
#include <iomanip>
#define LL long long
using namespace std;
int const N=1e5+5;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		cout<<k+(k-1)/(n-1)<<endl; 
	}
    return 0;
}
原创文章 90 获赞 36 访问量 6934

注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: