类欧几里得算法（部分）

##Preface
欧几里得算法，就是辗转相除法。
gcd(i,j)=gcd(j,i%j)

##定义
定义函数

##推导一波
显然当或者时，

若当a,b均小于c怎么办？
据大佬说转换成几何意义就是一条直线与x轴、y轴以及围成的直角梯形中的整点个数

枚举纵线，
原式可化为
设就是上面式子i=n时的数

枚举每个数

尽量化成j=0

大于等于下整除和不整除是一样的

变换一下

注意这里没有取整

大于等于，因为左边是整数
分子减1，符号变成大于

交换主体

然后里面的sigma可以撤掉


所以

如果只看a,c二维，变换是和欧几里得算法一样的
复杂度也和欧几里得算法一样

可以递归处理
边界条件是a=0，式子很明显。

g和h本蒟蒻并不会推，可以看看大佬的BLOG

##模版

LL fd(LL a,LL b,LL c,LL n)
{
  if(a==0) return((b/c)*(n+1));
  if(a>=c||b>=c) return fd(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
  LL m=(a*n+b)/c;
  LL v=fd(c,c-b-1,a,m-1);
  return n*m-v;
}