代码源每日一题-历法(结论数学)

代码源每日一题-历法(结论数学),第1张

原题链接

#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 1m,d,w109

题解

i i i 个月第 j j j天的星期数可以表示为 ( ( i − 1 ) × d + j ) m o d    w ((i-1)\times d+j)\mod w ((i1)×d+j)modw
j j j 个月第 i i i天的星期数可以表示为 ( ( j − 1 ) × d + i ) m o d    w ((j-1)\times d+i)\mod w ((j1)×d+i)modw
可以化为如下形式:
i × ( d − 1 ) + i + j + d i \times (d-1)+i+j+d i×(d1)+i+j+d
j × ( d − 1 ) + i + j + d j \times (d-1)+i+j+d j×(d1)+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×(d1)j×(d1)(modw)
由公式 a ≡ b ( m o d    c ) a \equiv b (\mod c) ab(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}) gagb(modgc) i × ( d − 1 ) m o d    w i \times (d-1) \mod w i×(d1)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();
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/914949.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表(0条)

保存