Codeforces #272 Div1 A. Dreamoon and Sums

CF272には開始時間に準備が間に合わず不参加。
まぁ練習の出来から見て出たらレート落としてそうではあったけど。
http://codeforces.com/contest/477/problem/A

問題

正の整数a,bが与えられる。
同じく正の整数xのうち、x%bが非0かつceil(x/b)/(x%b)==kかつkが1～aの範囲の整数となるものの総和を求めよ。

解法

x = p*b+qとする。
ceil(x/b)/(x%b) = p/q = kよりp=k*qなので、x = k*q*b+q = q*(1+k*b)。

あとは1≦q≦(b-1)かつ1≦k≦aにおけるxを列挙して和を取ればよい。
単に等差数列の総和を求めるだけなのでO(1)で処理可能で、(b*(b-1)/2)*(a+b*a*(a+1)/2)となる。

ll A,B;
ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	ll ret;
	cin>>A>>B;
	ret=B*(B-1)/2%mo;
	ret*=(A+A*(A+1)/2%mo*B)%mo;
	cout << ret%mo << endl;
	
}

まとめ

変わった問題だな。
時間設定が1.5sだけど、O(A)かO(B)の想定解もあるのかな。