代码源每日一题-历法（结论/数学）

#913.历法

给定 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 数据范围： 1 ≤ m , d , w ≤ 1 0 9 1leq m,d,wleq10^9 1≤m,d,w≤109

第 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)modw
第 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)modw
可以化为如下形式：
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 由公式 a ≡ b ( m o d    c ) a equiv b (mod c) a≡b(modc) 且 g = g c d ( a , b , c ) g=gcd(a,b,c) g=gcd(a,b,c)，则 a g ≡ b g ( m o d    c g ) frac{a}{g} equiv frac{b}{g} (mod frac{c}{g}) ga​≡gb​(modgc​) 得 i × ( d − 1 ) m o d    w i times (d-1) mod w i×(d−1)modw 的循环周期为 w g c d ( w , m i n ( d , m ) ) frac{w}{gcd(w,min(d,m))} gcd(w,min(d,m))w​

#include 

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();
}