Codeforces ECR #070 : F. You Are Given Some Letters...

こういう問題と解法どこから思いつくんだろうな。
https://codeforces.com/contest/1202/problem/F

問題

整数a,bが与えられる。
文字Aをa個、Bをb個から構成される文字列Sの集合を考える。
各文字列に対しS[i]=S[i mod K]が成り立つ最小のKを考えたとき、Kは何通りがあり得るか。
(Kは(a+b)の約数でなくてもよい)

解法

文字列に対しKが条件を満たすケースを考える。
そうすると周期g=floor(N/K)となる。
1周期分にあるA,Bの数をCa,Cbとすると、以下を満たす必要がある。
下2つの条件は、周期から余った分の埋め方に関するものである。

• Ca + Cb = K
• a - g*ca ≦ ca
• b - g*cb ≦ cb

a,bは0ではないのCa,Cbは1以上である。
なので上記式を満たせば、周期がちょうどKになるものが作れる(K未満のKの約数にならないようにできる)。

あとはgが一致する一連のKにおいて、下2つの式を見ると、Ca,Cbが満たすべき範囲を求めることができる。
gは高々√K通りなので、この問題はO(√A+B)で解ける。

ll A,B,C;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	C=A+B;
	ll ret=0;
	ll R=C;
	while(R>0) {
		ll H=C/R;
		ll L=C/(H+1)+1;
		ll AH=A/H;
		ll BH=B/H;
		ll AL=(A+H)/(H+1);
		ll BL=(B+H)/(H+1);
		if(AH>=AL && BH>=BL) {
			ret+=max(0LL,min(R,AH+BH)-max(L,AL+BL)+1);
			//cout<<L<<" "<<R<<" "<<ret<<endl;
		}
		R=L-1;
	}
	
	cout<<ret<<endl;
}

まとめ

解法みるとさっくりだけど、自分で思いつく気がしない。