##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;
}