AtCoder ARC #050 : C - LCM 111

WA多かったけど、あってもなくても順位変わらなかった。
http://arc050.contest.atcoder.jp/tasks/arc050_c

問題

1がA桁連続してできる整数xと、1がB桁連続してできる整数yの最小公倍数をMで割った余りを求めよ。

解法

AとBの最大公約数をGとする。
xとyの最大公約数をzとすると、zは1がG桁連続してできる整数となる。
LCM(x,y)=(x/z)*(y/z)*zなので、x/z, y/z, zそれぞれをMで割った余りを考えよう。

以下のような関数fを考える。
f(N,S) := 1が1の位からS桁おきに計N回登場するような整数をMで割った余り

例えばf(5,3)は1001001001001をMで割った余りである。
この関数を用いるとx/z, y/z, zをMで割った余りはそれぞれ以下のように表現できる。

• zは1がG回連続して続く整数なので、zをMで割った余りはf(G,1)。
• x/zは1がG桁おきに計A/G回登場してできる整数なので、xをMで割った余りはf(A/G,G)。
• y/zは同様にf(B/G,G)。

例えばA=15,B=9ならx=111111111111111、y=111111111なのでG=3、z=111、x=1001001001001、y=1001001となる。
あとはf(3,1)*f(5,3)*f(3,3)を求めればよい。

これで問題はf(N,S)を求める問題となった。
これはバイナリ法の要領で解ける。

• N==1ならf(N,S) = 1
• Nが2で割り切れるなら、半分の桁のものを求めて連結すればいいので、f(N/2,S)*(10^(N/2*S)+1)
• Nが2で割り切れないなら、f(N-1,S)*(10^S)+1

ll A,B,mo;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll gogo(ll d,ll step) {
	if(d<=1) return d;
	
	ll v=gogo(d/2,step);
	v = ((v*modpow(step,d/2)%mo)+v)%mo;
	if(d%2==0) return v;
	else return (v*step+1)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>mo;
	ll G=__gcd(A,B);
	
	ll X=gogo(G,10);
	ll Y=gogo(A/G,modpow(10,G));
	ll Z=gogo(B/G,modpow(10,G));
	cout<<X*Y%mo*Z%mo<<endl;
}

まとめ

方針は割とすぐ立ったけど、細かいミスをしてしまった。