Codeforces ECR #092 : E. Calendar Ambiguity

ちょこちょこCFも進めないとね…。
https://codeforces.com/contest/1389/problem/E

問題

正整数M,D,Wが与えられる。
この地のカレンダー、M月まであり、各月D日まである。また、W個の曜日がある。

整数対(x,y)が曖昧であるとは、x月y日とy月x日が一致することを意味する。
x＜yとなる整数対のうち、曖昧なものは何通りか。

解法

1始まりだとややこしいので、月も日も0始まりとする。
条件を満たすには(xD+y)≡(yD+x) (mod W)なので、(y-x)(D-1)≡0 (mod W)となる(y,x)を求めればよい。
W'をWをGCD(D-1,W)で割った値とすると、y-xがW'の倍数なら条件を満たす。
あとはそのようなx,yを数え上げよう。

int T;
ll M,D,W;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>M>>D>>W;
		
		if(D==1) {
			cout<<0<<endl;
			continue;
		}
		ll G=__gcd(W,D-1);
		
		W/=G;
		
		ll ret=0;
		x=min(M,D)-1;
		
		if((x+1)%W==0) {
			ll a=(x+1)/W;
			ret=a*(a-1)/2*W;
		}
		else {
			ll a=(x+1)/W;
			ll m=(x+1)%W;
			ret=a*(a+1)/2*m+a*(a-1)/2*(W-m);
		}
		
		
		cout<<ret<<endl;
		
	}
}

まとめ

だいぶ曖昧だ。