CF 1379 B. Dubious Cyrpto

佚名 4年前 (2020-07-21) 算法 849人围观抢沙发百度已收录

传送门

题目：给定一个区间范围[l, r]和m，在区间[l, r]中取a, b, c，使得 na + b - c = m（n > 0）。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：na + b - c = m，可以看出a和n都是整数,则：

na + b - c = m -> na = m - b + c

b,c∈[l, r] -> na ∈ [m + l - r, m + r - l]

则我们需要找到一个na存在于区间[m + l - r, m + r - l]，a∈[l, r]，我们可以枚举a，对于该a：

如果：①m / a * a >= m + l - r 且 m / a * a 一定满足小于等于m，则我们把m - (m / a) * a用b,c∈[l, r]凑出来。

否则：②(m / a + 1) * a <= m + r - l 且 (m / a + 1) * a一定满足大于等于m，则我们把m - (m / a + 1) * a用b,c∈[l, r]凑出来

当然有一种特殊情况：③ m < l,则直接 a = l, c = r, b = m - l + r

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 #include <cmath>
 7  
 8 using namespace std;
 9  
10 #define ll long long
11 #define pb push_back
12 #define fi first
13 #define se second
14 
15 const int N = 2e5 + 10;
16 char s[N];
17 int len;
18 
19 void solve()
20 {   
21     int T;
22     cin >> T;
23     while(T--){
24         
25         ll l, r, m, a, b, c;
26         cin >> l >> r >> m;
27         
28         if(m < l){
29             a = l;
30             c = r;
31             b = m + r - l;
32             cout << a << " " << b << " " << c << endl;
33             continue;
34         }
35 
36         ll ml = m + l - r;
37         ll mr = m + r - l;
38         for(int i = l; i <= r; ++i){
39             ll times = m / i;
40             if(times * i < ml){
41                 if((times + 1) * i <= mr){
42                     a = i;
43                     ll remains = (times + 1) * i - m;
44                     b = l;
45                     c = l + remains;
46                     break;
47                 }
48             }else if(times * i >= ml){
49                 ll remains = m - (times * i);
50                 a = i;
51                 b = r;
52                 c = r - remains;
53                 break;
54             }
55         }
56 
57         cout << a << " " << b << " " << c << endl;
58     }
59 }
60  
61 int main()
62 {
63     ios::sync_with_stdio(false);
64     cin.tie(0);
65     cout.tie(0); 
66     solve();
67  
68     return 0;
69 }