526互联

Educational Codeforces Round 129 (Rated for Div. 2)

发布时间 2023-11-01 00:12:57作者: gan_coder

Educational Codeforces Round 129 (Rated for Div. 2)

B可以看作一个无限长的序列由a进行重复拼接，我们直接计算一下是哪个即可。
C判断无解之后直接模拟即可
D IDA*就行每次从大到小搜，实际非常快。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef __int128 i128;
typedef double db;
typedef long long ll;
const int mo=998244353;
const int N=2e5+5;
ll n,x,len,d;
i128 mx;
int get(i128 x){
	int l=0;
	while (x) {
		x/=10;
		l++;
	}
	return l;
}
bool dfs(i128 x,ll y){
	ll t;
	if (get(x)+d-y<n) return 0;
	if (get(x)>n) return 0;
	if (get(x)==n) return 1;
	
	if (y==d) return 0;
	bool bz[10];
	memset(bz,0,sizeof(bz));
	
	t=x;
	while (t) {
		bz[t%10]=1;
		t/=10;
	}
	
	fd(i,9,2) if (bz[i]) {
		if ((__int128)i*(__int128)x>mx) continue;
		
		if (dfs(i*x,y+1)) return 1;
	}
	return 0;
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);

	scanf("%lld %lld",&n,&x);
	
	mx=1;
	fo(i,1,n+1) mx=mx*(i128)10;
	
	ll t=x;
	
	bool flag=0;
	while (t) {
		len++;
		if (t%10>1) flag=1;
		t/=10;
	}
	
	if (!flag) {
		if (len!=n) puts("-1");
		else puts("0");
		return 0;
	}
	
	if (len>n) {
		puts("-1");
		return 0;
	}
	
	for (d=n-len;;d++ ) {
		if (dfs(x,0)){
			printf("%lld",d);
			return 0;
		}
	}

	return 0;
}