按需取余

ACM算法日常

发布于 2020-07-27 09:43:07

2.1K0

发布于 2020-07-27 09:43:07

CF 1374A. Required Remainder

You are given three integers x,y and n. Your task is to find the maximum integer k such that 0≤k≤n that kmodx=y, where mod is modulo operation. Many programming languages use percent operator % to implement it.

给定3个整数x,y和n，找到一个数k，使得

0 \leqslant k \leqslant n

，并且

k \% x=y

。

In other words, with given x,y and n you need to find the maximum possible integer from 0 to n that has the remainder y modulo x.

You have to answer t independent test cases. It is guaranteed that such k exists for each test case.

给定t组测试数据，每组数据保证存在这样的k。

Input

The first line of the input contains one integer t (1≤t≤5⋅104) — the number of test cases. The next t lines contain test cases.

The only line of the test case contains three integers x,y and n (2≤x≤109; 0≤y<x; y≤n≤109).

It can be shown that such k always exists under the given constraints.

Output

For each test case, print the answer — maximum non-negative integer k such that 0≤k≤n and kmodx=y. It is guaranteed that the answer always exists.

Example

输入

7
7 5 12345
5 0 4
10 5 15
17 8 54321
499999993 9 1000000000
10 5 187
2 0 999999999

输出

比如输入x=7，y=5，n=12345，如何求得k，使得k<12345并且k%7=5呢？

朴素的做法：遍历n到1，看k%7是否等于5

换一种思路：考虑p%7是否等于0，如果等于0，p再加上5不就是答案k了吗。显然直接用n/b取底再乘以b即是最大的p。结果可以用公式表示如下：

k = \lfloor n \div x \rfloor *x + y

当我们在解决一个问题的时候，首先看能不能将这个问题转换为相近的问题，间接的去思考最终结果，虽然是一个很小的题目，但是可以多花一点时间思考为什么。

每天学习一点点，你学会了吗，这是CF最简单的题目啦，加油~

源代码：C++

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ff first
#define ss second
typedef long long ll;
ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    cin>>t;
    while(t--){
        ll x,y,n;
        cin>>x>>y>>n;
        ll val=n/x;
        if(val*x+y<=n){
            cout<<(val*x+y)<<"\n";
        }
        else{
            cout<<(val*x+y-x)<<"\n";
        }
    }
    return 0;
}