[求助]Atcoder ABC235 D题无法通过第四个样例

#include <bits/stdc++.h>
using namespace std;
#define int long long
int cur=0x3f3f3f3f;
int a,n;
string str;
string tmp;
int tmp2;
void dfs(int step,int ans,bool flag)
{
	//cout<<"ans: "<<ans<<endl;
	if(step>cur)return;
	if(ans>=10000000)return;
	if(ans==n)
	{
		cur=min(cur,step);
		return;
	}
	if(!flag)
	{
		dfs(step+1,ans*a,1);
		return;
	}
	dfs(step+1,ans*a,1);
	if(ans%10==0)return;
	str=to_string(ans);
	tmp="";
	tmp+=str[str.size()-1];
	for(int i=0;i<str.size()-1;i++)tmp+=str[i];
//	cout<<"tmp: "<<tmp<<endl;
	tmp2=atoi(tmp.c_str());
//	cout<<tmp2<<endl;
	dfs(step+1,tmp2,0);
}
signed main()
{
	
	scanf("%d%d",&a,&n);
	//if(a==2&&n==767090)
///	{
	//	cout<<111;
	//	return 0;
//	}
	dfs(0,1,1);
	dfs(0,1,0);
	if(cur==0x3f3f3f3f)
	{
		printf("-1\n");
		return 0;
	}
	printf("%d",cur);
	return 0;
}