1650B. DIV + MOD

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output Not so long ago, Vlad came up with an interesting function:

f $_{a}$ (x)=⌊ $x\over a$ ⌋+x mod a, where ⌊ $x\over a$ ⌋ is $x\over a$ , rounded down, x mod a — the remainder of the integer division of x by a. For example, with a=3 and x=11, the value f $_{3}$ (11)=⌊ $11\over 3$ ⌋+11 mod 3=3+2=5.

The number a is fixed and known to Vlad. Help Vlad find the maximum value of fa(x) if x can take any integer value from l to r inclusive (l≤x≤r).

Input

The first line of input data contains an integer t (1≤t≤10 $^{4}$ ) — the number of input test cases.

输入数据的第一行包含一个整数t（1≤T≤10 $^{4}$ ）-输入测试用例的数量。

This is followed by t lines, each of which contains three integers l $_{i}$ , r $_{i}$ and a $_{i}$ (1≤l $_{i}$ ≤r $_{i}$ ≤10 $^{9} i$ ,1≤ai≤10 $^{9}$ ) — the left and right boundaries of the segment and the fixed value of a.

然后是t行，每行包含三个整数l $_{i}$ 、r $_{i}$ 和a $_{i}$ (1≤l $_{i}$ ≤r $_{i}$ ≤10 $^{9} i$ ,1≤ai≤10 $^{9}$ )-段的左右边界和a的固定值。

Output

For each test case, output one number on a separate line — the maximum value of the function on a given segment for a given a.

对于每个测试用例，在单独的一行上输出一个数字——给定a的给定段上函数的最大值。

Example

input

1 4 3

5 8 4

6 10 6

1 1000000000 1000000000

10 12 8

output

999999999

Note

In the first sample:

f $_{3}$ (1)=⌊ $1\over3$ ⌋+1mod3=0+1=1,

f $_{3}$ (2)=⌊ $2\over3$ ⌋+2mod3=0+2=2,

f $_{3}$ (3)=⌊ $3\over3$ ⌋+3mod3=1+0=1,

f $_{3}$ (4)=⌊ $4\over3$ ⌋+4mod3=1+1=2

As an answer, obviously, f $_{3}$ (2) and f $_{3}$ (4) are suitable.

Solution

考虑到x/a每增大a才增大1，xmoda每增大1增大1，周期为a，值域为[0,a-1]，因此考虑最接近r端点模a余数最大值（可以为r），能保证总体最大值

Code

#include <iostream>
using namespace std;

//B. DIV + MOD
int main() {
    int t = 0;
    cin >> t;
    for (int i = 0;i < t;i++){
        int l,r,a = 0;
        cin >> l >> r >> a;
        if(r % a == a - 1)//r%a是a-1
            cout << r / a + r % a << endl;
        else if(r - r % a - 1 >= l)//r最近%a是a-1的值＞=l
            cout << (r - r % a - 1 ) / a + (r - r % a -1) % a << endl;
        else//r最近%a是a-1的值<l
            cout << r / a + r % a << endl;
    }
    return 0;
}

CodeForces 文章被收录于专栏

https://codeforces.ml/