原题链接
题意
给定
m
m
m
,
d
d
d
,
w
w
w
, 代表某国每一年都有
m
m
m
个月 , 每个月有
d
d
d
天。每个星期有
w
w
w
天。每年的第一天也是一个星期的第一天。
求出有多少对
(
x
,
y
)
(x,y)
(
x
,
y
)
, 满足
x
<
y
x<y
x
<
y
且 第
y
y
y
个月的第
x
x
x
天和第
x
x
x
个月的第
y
y
y
天在一个星期内是同一天。
数据范围：
1
≤
m
,
d
,
w
≤
1
0
9
1\leq m,d,w\leq10^9
1
≤
m
,
d
,
w
≤
1
0
9
题解
第
i
i
i
个月第
j
j
j
天的星期数可以表示为
(
(
i
−
1
)
×
d
+
j
)
m
o
d
w
((i-1)\times d+j)\mod w
(
(
i
−
1
)
×
d
+
j
)
m
o
d
w
第
j
j
j
个月第
i
i
i
天的星期数可以表示为
(
(
j
−
1
)
×
d
+
i
)
m
o
d
w
((j-1)\times d+i)\mod w
(
(
j
−
1
)
×
d
+
i
)
m
o
d
w
可以化为如下形式：
i
×
(
d
−
1
)
+
i
+
j
+
d
i \times (d-1)+i+j+d
i
×
(
d
−
1
)
+
i
+
j
+
d
j
×
(
d
−
1
)
+
i
+
j
+
d
j \times (d-1)+i+j+d
j
×
(
d
−
1
)
+
i
+
j
+
d
所以只需要找出所有
(
i
,
j
)
(i, j)
(
i
,
j
)
满足
i
<
j
i<j
i
<
j
且
i
×
(
d
−
1
)
≡
j
×
(
d
−
1
)
(
m
o
d
w
)
i \times (d-1) \equiv j \times (d-1) (\mod w)
i
×
(
d
−
1
)
≡
j
×
(
d
−
1
)
(
m
o
d
w
)
由公式
a
≡
b
(
m
o
d
c
)
a \equiv b (\mod c)
a
≡
b
(
m
o
d
c
)
且
g
=
g
c
d
(
a
,
b
,
c
)
g=gcd(a,b,c)
g
=
g
c
d
(
a
,
b
,
c
)
，则
a
g
≡
b
g
(
m
o
d
c
g
)
\frac{a}{g} \equiv \frac{b}{g} (\mod \frac{c}{g})
g
a
≡
g
b
(
m
o
d
g
c
)
得
i
×
(
d
−
1
)
m
o
d
w
i \times (d-1) \mod w
i
×
(
d
−
1
)
m
o
d
w
的循环周期为
w
g
c
d
(
w
,
m
i
n
(
d
,
m
)
)
\frac{w}{gcd(w,min(d,m))}
g
c
d
(
w
,
m
i
n
(
d
,
m
)
)
w
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int m, d, w;
int get(int x) {
return x * (x-1) / 2;
}
void slv() {
cin >> m >> d >> w;
int res = 0;
m = min(m, d);
d --;
int cir;
cir = w / __gcd(w, d);
int p = m/cir, q = (m%cir + cir)%cir;
cout << (cir - q) * get(p) + q * get(p + 1) << '\n';
}
signed main() {
int _; cin >> _;
while ( _--)
slv();
}