[CSP模拟测试43、44]题解

状态极差的两场。感觉现在自己的思维方式很是有问题。

(但愿今天考试开始的一刻我不会看到H I J)

A

考场上打了最短路+贪心，水了60。

然而正解其实比那30分贪心好想多了。

进行n次乘法后的结果一定可以化成$S\times b^n + m\times a$的形式，并且$m$是b的若干次幂(带系数)之和。

也就是说，$m=\frac{T-S\times b^n}{a}$可以写成$b$进制数，当然前提是$T-S \times b^n \ mod\ a=0$。

那么这个b进制数的系数之和其实就是加法操作的次数，这个很好理解。

枚举乘法次数，然后得到相应的$m$后直接$b$进制拆解，注意要从高次开始。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll S,T,a,b,ans=1e15;
int main()
{
    scanf("%lld%lld%lld%lld",&S,&T,&a,&b);
    for(ll n=0,now=1;S*now<=T;n++,now*=b)
    {
        ll m=T-S*now,res=0;
        if(m%a)continue;
        m/=a;
        ll c=now;
        while(m)res+=m/c,m%=c,c/=b;
        res+=n;
        ans=min(ans,res);
    }
    cout<<ans<<endl;
    return 0;
}