CF1374A Required Remainder 题解

CSDN同步

原题链接

简要题意：

(T) 组询问，求 (leq n) 的最大的 (k) 使得 (k\% x = y) 的 正整数。

(T leq 5 imes 10^4 , x,y,n leq 10^9).

这题挺简单的，主要是考察思维能力。

一个方法是，先找出 (k \% x = 0) 的最大值，再加上 (y).

这个方法的答案是 (lfloor frac{n}{x} floor imes x + y)，但是你发现这个值可能会超过 (n).

比方说 (n=7 , x=3 , y=2)，求出来是 (8)，这种情况我们需要把答案再减去一个 (x)，即 (5)，不影响答案。

具体实现过程：

我们先求出 (t = n \% x).

如果 (t geq y)，那么我们直接 (n-t+y) 就可以得到答案。

但是如果 (t<y)，我们用 (n-t-x+y) 即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}

inline void write(int x) {
	if(x<0) {putchar('-');write(-x);return;}
	if(x<10) {putchar(char(x%10+'0'));return;}
	write(x/10);putchar(char(x%10+'0'));
}

int main() {
	int T=read(); while(T--) {
		int x=read(),y=read(),n=read();
		int k=n%x; if(k>=y) printf("%d
",n-k+y);
		else printf("%d
",n-k-x+y);
	}
	return 0;
}