P9560 [SDCPC2023] E-Math Problem

思路

首先发现应该优先除，理由很简单，如果先乘以 \(k\) 再加上一个不超过 \(k\) 的值，那么除以 \(k\) 后，就除回去了，没有发生任何变化。

所以我们可以先枚举除以多少次 \(k\)，得到除以这么多次 \(k\) 后的 \(n\)。我们再进行若干次乘法，计算 \(n\) 的取值范围 \([l,r]\)，那么只要这个区间包含了 \(m\) 的倍数就行。

易知对 \(n\) 进行 \(x\) 次乘法操作后的取值区间是 \([k^x\times n,k^{x+1}\times n-1]\)。

所以我们可以只记录区间左端点 \(l\) 和区间长度 \(len\)，这是为了方便后面的取模操作判断是否包含 \(m\) 的倍数。

因为只要包含倍数，所以左端点 \(l\) 可以模 \(m\)，这样 \(l+len\geq m\) 或者 \(m-l\leq len\) 就代表满足条件，记录下次数就可以得到答案，然后取最小值就可以了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
long long T,n,k,m,a,b,ans,res,cnt,l,len,rp;
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld%lld",&n,&k,&m,&a,&b);
		if(n%m==0){printf("0\n");continue;}//直接满足条件
		if(k==1){printf("-1\n");continue;}//乘以和除以都没用，所以无解
		ans=0x3f3f3f3f3f3f3f3f,cnt=rp=0;
		while(1)
		{
			l=n%m,len=1,res=cnt;//此处的len多了1，方便计算，判断也只需要把>=变成>即可
			for(int i=1;;++i)
			{
				if(len>(m-l)%m){ans=min(ans,res);break;}//满足条件
				res+=a,l*=k,len*=k,l%=m;//进行一次乘法操作
			}
			if(!n) break;//n为0也算满足条件，同时也不用继续进行除法操作
			n/=k,cnt+=b;
		}
		printf("%lld\n",ans);
	}
}