C++11(clang++ 3.9) 解法, 执行用时: 96ms, 内存消耗: 83064K, 提交时间: 2020-08-28 18:57:16

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
struct Hash_table {
	static const int V=10000003;
	int fst[V],nxt[V];
	int ctm,ptm[V],T;
	int val[V];
	int key[V];
	void init() { T=0; ctm++;}
	void insert(int s,int v) {
		int S=s%V;
		if (ptm[S]!=ctm) ptm[S]=ctm,fst[S]=-1;
		for (int j=fst[S];j!=-1;j=nxt[j]) if (key[j]==s) return;
		nxt[T]=fst[S],fst[S]=T,key[T]=s,val[T]=v;
		T++;
	}
	int query(int s) {
		int S=s%V;
		if (ptm[S]!=ctm) return -1;
		for (int j=fst[S];j!=-1;j=nxt[j]) if (key[j]==s) 
			return val[j];
		return -1;
	}
}hs;

const int N=101000;
int n;
ll a,b,c[N],l,r;
char s[N];


void init() {
	memset(c,0,sizeof(c));
	n=strlen(s);
	rep(i,0,n) c[i]=s[n-1-i]-'0';
	rep(i,0,n) c[i]=c[i]*b;
	rep(i,0,n) c[i+1]+=c[i]/10,c[i]%=10;
	int m=n;
	while (c[m]>0) {
		c[m+1]+=c[m]/10;
		c[m]%=10;
		m++;
	}
	l=0;
	per(i,n,m) l=l*10+c[i];
	bool ze=0;
	rep(i,0,n) if (c[i]) ze=1;
	l+=ze;
	memset(c,0,sizeof(c));
	rep(i,0,n) c[i]=s[n-1-i]-'0';
	c[0]++;
	rep(i,0,n) c[i]=c[i]*b;
	c[0]--;
	rep(i,0,n) c[i+1]+=c[i]/10,c[i]%=10;
	m=n;
	while (c[m]>0) {
		c[m+1]+=c[m]/10;
		c[m]%=10;
		m++;
	}
	r=0;
	per(i,n,m) r=r*10+c[i];
	if (l>r) {
		puts("-1");
		exit(0);
	} 
}
int T=50,G=300;
int main() {
	scanf("%lld%lld",&a,&b);
	ll d=gcd(a,b);
	a/=d; b/=d;
	a%=b;
	scanf("%s",s);
	init();
	ll z=a;
	rep(i,0,1000000) {
		if (l<=z&&z<=r) {
			printf("%d\n",i+1);
			return 0;
		}
		z=z*10%b;
	}
	rep(i,0,T) {
		a=a*10%b;
		ll d=gcd(a,b);
		a/=d; b/=d;
	}
//	printf("%lld %lld %lld %lld\n",a,b,l,r);
	init();
	assert(gcd(b,10)==1);
	G=max(300.,sqrt(1.*b/(r-l+1)));
	int M=b/G+100;
	ll g=1;
	hs.init();
	rep(i,0,G) g=g*10%b;
	rep(i,1,M) {
		a=a*g%b;
		hs.insert(a,T+G*i);
	}
//	printf("%d %d\n",l,r);
	int ret=1<<30;
	rep(c,l,r+1) {
		ll k=c;
		rep(i,0,G) {
			int w=hs.query(k);
			if (w!=-1) ret=min(ret,w-i+1);
			k=k*10%b;
		}
	}
	if (ret==(1<<30)) ret=-1;
	printf("%d\n",ret);
}