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

原题链接

#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 xx<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≤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 ii<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)(modw)
由公式 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();
}