2020ICPC沈阳I - Rise of Shadows

剩余系

Problem - I - Codeforces

题意

给定 \(H,M,A\)

\(2<=H,M<=10^9,\;0<=A<=\frac {H*M}2\)

假设一个钟表有 \(H\) 小时，一小时有 \(M\) 分钟，求一天中有多少整数分钟，满足时针、分钟夹角不超过 \(\frac {2\pi A}{HM}\)

思路

时针角速度：\(v_h=\frac {2\pi}{HM}\)，分针角速度： \(v_m=\frac {2\pi}{M}\)
设 \(t\) 分钟时 \((v_m-v_h)*t\equiv \frac {2\pi A}{HM}\pmod {H*M}\)

即 \((H-1)*t\equiv A \pmod {H*M}\)，求有多少个 \(t\) 满足 \((H-1)*t \mod ({H*M})<=A\)
在 \(ax\equiv b\pmod m\) 中，令 \(g=\gcd(a,m)\)

则 \(x\in[0,m-1]\)，在模 m 意义下 \(a*x\) 有 \(g\) 轮循环，每轮有 \(0,a,2*a...\) 等 \(\lfloor\frac mg\rfloor+1\) 种取值
因此模为 \([1,A]\) 有 \(\frac Ag\) 种取值
对称地，模为 \([H*M-A,H*M-1]\) 与 \([1,A]\) 的 \(x\) 取值的对应，也有 \(\lfloor\frac Ag\rfloor\) 个，再假设模为 0 恒有一个
有 \(g\) 轮循环，答案为 \(ans=(\lfloor\frac Ag\rfloor*2+1)*g\)
注意特判，当 \(A == \frac {HM}2\) 时，所有分钟都是，即有 \(H*M\) 个，但按上述算法，由于 \(A==H*M-A\) ，会多算一个

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll H, M, A;

ll gcd(ll a, ll b)

{

	if (b == 0)

		return a;

	return gcd(b, a % b);

}

ll solve()

{

	if (A * 2 == H * M)

		return H * M;

	ll a = H - 1, m = H * M;

	ll g = gcd(m, a);

	ll ans = (A / g * 2 + 1) * g;

	return ans;

}

int main()

{

	cin >> H >> M >> A;

	cout << solve() << endl;

	return 0;

}

巴特西

2020ICPC沈阳I - Rise of Shadows

剩余系

题意

思路

代码

最新文章

热门文章