为了ccpc网络赛组了新队伍，拉了icpc2020沈阳来训练，然后被爆艹了。补题时学的新东西。

题意：给你一个H，一个M，一个A。一天有H个小时，一小时有M分钟，问你一天之内有多少整数分钟，时针和分针的角度差小于等于A

撕烤一下这个题目，就是在一个H大格，HM小格的表盘上，分针每分钟走H小格，时针每分钟走M小格，问相差A小格的整数分钟的数目。
呢么可以构造不等式：
_ $abs(kH\mathrm{\%}(HM)-k)<=A$

_ $iHM-A\le k(H-1)\le iHM+A$

其中k是第k分钟，i是指分针已经走过了i圈，
所以我们只需要求满足不等式的(k,i)二元组的个数即可。
这时候就用到了类欧几里得算法，这个算法可以在$O(logn)$时间内得到 $F(a,b,c,n)=\sum _{i=0}^n\lfloor \frac{a\ast i+b}{c}\rfloor$，形象的理解可以理解为一条直线与x=0,y=0,x=n.四条直线围成的直角梯形区域有多少整点。
算法的详细推导
板子来源

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f(ll a, ll b, ll c, ll n) 
{
	if(!a) return b/c*(n+1);
	if(a>=c||b>=c)
	return f(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
	ll m=(a*n+b)/c;
	return n*m-f(c,c-b-1,a,m-1);
}
int main()
{
	ll h,m,a;
	scanf("%lld%lld%lld",&h,&m,&a);
	ll ans1=f(h*m,a+h*m,h-1,h-3 );
	ll ans2=f(h*m,-a+h*m-1,h-1,h-3 );
	ll ans=ans1-ans2;
	ans+=(1+a/(h-1))*2;
	ans--;
	
	ans=min(ans,h*m);//特判A=HM/2的情况
	printf("%lld\n",ans);
	return 0;
}
Copy