Codeforces ECR #144 : F. Strange Triples

本番中の正答者がずいぶん少ない。
https://codeforces.com/contest/1796/problem/F

問題

整数の組a,b,nがstrangeであるとは、an/nb=a/bであるものを意味することとする。
なお、an, nbはaとn、nとbを文字列的に連結した値とする。

今3整数A,B,Nが与えられる。1≦a＜A、1≦b＜B、1≦n＜Nであるようなstrangeな整数の組(a,b,n)は何通りか。

解法

gをGCD(a,b)とし、a',b'をa,bをgで割ったものとする。
元の式を変形するとnはa'で割れないといけないので、n'=n/a'とする。

式変形を続けるとb'=a'*10^|b|-b(10^|n|-1)/n'となる。
n'=k1*k2とし,bをk1の倍数で(10^|n|-1)をk2の倍数であるものとする。
k2のバリエーションはさほど多くないので、k2を総当たりしよう。

ll A,B,N;
ll p10[11];
int dlen[100001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	p10[0]=1;
	FOR(i,10) p10[i+1]=p10[i]*10;
	for(i=0;i<=5;i++) for(j=p10[i];j<=100000;j++) dlen[j]++;
	
	int pat=0;
	set<pair<ll,ll>> R;
	for(int nlen=1;nlen<=9;nlen++) {
		ll p9=p10[nlen]-1;
		vector<int> Ks;
		for(int a=1;a*a<=p9;a++) if(p9%a==0) {
			Ks.push_back(a);
			if(a*a!=p9) Ks.push_back(p9/a);
		}
		
		FORR(k2,Ks) {
			int r=p9/k2;
			for(int d=1;d<100000;d++) {
				for(int lenb=dlen[d];lenb<=5;lenb++) {
					int bd=p10[lenb]-1LL*d*r%p10[lenb];
					int lb=(p10[lenb-1]+bd-1)/bd;
					int rb=(p10[lenb]-1)/bd;
					int dd=d/__gcd(d,bd);
					for(int g=(lb+dd-1)/dd*dd;g<=rb;g+=dd) {
						ll b=1LL*g*bd;
						if(b>100000) break;
						int k1=b/d;
						if(__gcd(k1,r)>1) continue;
						int ad=(1LL*d*r+bd)/p10[lenb];
						if(1LL*ad*g>100000) continue;
						ll n=1LL*k1*k2*ad;
						ll a=ad*g;
						if(to_string(n).size()==nlen) R.insert({a*1000000+b,n});
						
					}
				}
			}
		}
		
	}
	
	
	
	cin>>A>>B>>N;
	int num=0;
	FORR2(ab,n,R) {
		ll a=ab/1000000;
		ll b=ab%1000000;
		int nlen=to_string(n).size();
		if(a<A&&b<B&&n<N) {
			ll v=(a*p10[nlen]+n)*b;
			ll w=(n*p10[dlen[b]]+b)*a;
			if(v==w) num++;
		}
	}
	cout<<num<<endl;
	
}

まとめ

この式変形を本番中に詰めるのつらすぎるな。