题解：P10252 线性变换

· · 题解

P10252 线性变换

做这题的时候矛盾了很久。

审题：

给出三个非负整数 x,a,b。在 x \ge 0 的前提下，对 x 进行任意次（包括 0 次）操作，如下：

求通过操作能得到的 x 的最小值。

分析样例：

第一组：

输入：

6 2 4

输出：

6

手动模拟得操作数为 0。

第二组：

输入：

5 3 16

输出：

-1

手动模拟得操作数为 1。

分析做法：

通过题目：将 x 变为 ax - b 可以发现，其实进行一次操作后，x 所增加的值为 (a-1)x-b，由于我们需要最小值，所以要保证 (a-1)x < b。

设第一次增加的值为正整数 y。

那么这一次的 x 就等于 x+y。

下一次操作后就变化成 a(x+y)-b。

由于 y 为正整数，所以如果第一次的值增加，那么就说明往后的 x 一定是递增的，如果是减少，同理。

所以当 x 不等于 0 并且 a 不等于 0 时，x 的值一定是单调递增或者递减的。

根据我们刚才所得出的结论，我们可以通过判断第一次操作所变化的值，判断 x 递增或递减。

如果是递增，由于我们需要找的为最小值，所以选择不操作，这种就是样例中第一组的情况。

那如果是递减，那么我们就可以选择直接模拟至 x 成为防负数。

接下来就是判断几个特殊情况。

首先，是 a=1。

当 a=1 时，其实最小值就是不断减 b，直至 x 成为负数，可以使用取模直接得出结果，而如果直接模拟会耗费大量时间，因为每一次操作会且只会减去一个 b，取模能够省掉很多时间。

然后就是当 a=0 或 x=0。

当这种情况出现时，很显然，答案就是等于 -b。

处理矛盾：

我矛盾了很久的原因是不知道为什么可以直接模拟，难道不会超时吗？

其实可以发现，在排去特殊情况时，操作数一般都比较少，因为符合递减的情况下，x 每一次操作所减少的数也是逐渐递增的。

实现：

#include<bits/stdc++.h>
using namespace std;
long long T,x,a,b;
int main(){
    cin>>T;
    while(T--)
    {
        cin>>x>>a>>b;
        if(a==0 || x==0) x=-b; //分类讨论：x=0 并且 a=0 的情况。
        else if((a-1)*x>=b) x=x; //分类讨论：递增的情况。
        else if(a==1) x=x%b-b; //分类讨论：a=1的情况。
        else while(x>=0) x=x*a-b; //分类讨论：正常情况。
        cout<<x<<endl;
    }
    return 0;
}

感谢管理员的审核！