コドフォ Educational Contest 92 E Calendar Ambiguity 解説[python]

概要

全ての月がd 日であり、一年にm 日ある暦がある。
1週がw 日とすると、同じ年のx月y 日の曜日がy日x日の曜日と等しいようなx,y のpair( xはyより小さい )が何個あるかを数えよ。

制約

1 <= m,d,w <= 10**9

考察

x月y日は年始から数えて(x-1)*d + y日目なので、((x-1)*d + y) %w曜日となる

　そのため、条件を定式化すると

(d* (y-x)+ x-y ) %w == 0

でまとめると、
(x-y)(d-1) % w == 0 になるx,yを見つければいい。

この時、2種類に場合分けできて、

d == 1 の時

x,y は任意
m*(m-1)//2が答え

それ以外

y-x が w/gcd(d-1,w)で割り切れれば良い

m-1 >= w/gcd(d-1,w) * k を満たす任意の正の整数k に対して、ans += m - w/gcd(d-1,w) * k となるので、
m* k -w/gcd(d-1,w)*k*(k+1)//2

実装

import sys
import math


def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    return gcd(b % a, a)


read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    m, d, w = map(int, input().split())
    if d == 1:
        print(min(d, m) * (min(d, m) - 1) // 2)
    elif m == 1:
        print(0)
    else:
        div = w // gcd(w, d - 1)
        k = (min(m, d) - 1) // div
        # print(div, k, m, d, w)
        print(min(m, d) * k - div * k * (k + 1) // 2)