详见dalao的《洪华敦-类欧几里得算法》
这个算法的来源，可以形象化的理解为欧几里得算法的几何意义。
图详见上面的PPT。
对于一个平面，每个整点有一个价值，
如果需要求一条直线与坐标轴围成的部分的整点价值和，
设这条直线为 y = a x + b y=ax+b y=ax+b，那么可以通过PPT中的方法不断更换坐标轴递归求解。
推式子很烦。
但还是要推。
1.求 F ( a , b , c , n ) = ∑ i = 0 n ? a i + b c ? F(a,b,c,n) = \sum_{i=0}^n \lfloor\frac {ai+b}{c}\rfloor F(a,b,c,n)=∑i=0n??cai+b??
F ( a , b , c , n ) = ∑ i = 0 n ? ( a m o d     c ) i + ( b m o d     c ) c ? + i ? a c ? + ? b c ? F(a,b,c,n) = \sum_{i=0}^n \lfloor\frac {(a\mod c)i+(b\mod c)}c\rfloor + i\lfloor\frac ac\rfloor+\lfloor\frac bc\rfloor F(a,b,c,n)=∑i=0n??c(amodc)i+(bmodc)??+i?ca??+?cb??
设 ? ( a m o d     c ) n + ( b m o d     c ) c ? = M \lfloor\frac {(a\mod c)n+(b\mod c)}c\rfloor = M ?c(amodc)n+(bmodc)??=M
S n k = ∑ i = 0 n i k S_n^k = \sum_{i=0}^n i^k Snk?=∑i=0n?ik
F ( a , b , c , n ) = S n 1 ? a c ? + S n 0 ? b c ? + ∑ i = 0 n ? ( a m o d     c ) i + ( b m o d     c ) c ? = S n 1 ? a c ? + S n 0 ? b c ? + ∑ j = 0 M ? 1 ∑ i = 0 n [ j < ? ( a m o d     c ) i + ( b m o d     c ) c ? ] = S n 1 ? a c ? + S n 0 ? b c ? + ∑ j = 0 M ? 1 ∑ i = 0 n 1 ? [ j > = ? ( a m o d     c ) i + ( b m o d     c ) c ? ] = S n 1 ? a c ? + S n 0 ? b c ? + ( n + 1 ) M ? ∑ j = 0 M ? 1 ∑ i = 0 n [ j + 1 > ? ( a m o d     c ) i + ( b m o d     c ) c ? ] = S n 1 ? a c ? + S n 0 ? b c ? + ( n + 1 ) M ? ∑ j = 0 M ? 1 ∑ i = 0 n [ i ( a m o d     c ) < ( j + 1 ) c ? ( b m o d     c ) ] = S n 1 ? a c ? + S n 0 ? b c ? + ( n + 1 ) M ? ∑ j = 0 M ? 1 ∑ i = 0 n [ i ( a m o d     c ) < = ( j + 1 ) c ? ( b m o d     c ) ? 1 ] = S n 1 ? a c ? + S n 0 ? b c ? + ( n + 1 ) M ? ∑ j = 0 M ? 1 ∑ i = 0 n [ i < = ? ( j + 1 ) c ? ( b m o d     c ) ? 1 a m o d     c ? ] = S n 1 ? a c ? + S n 0 ? b c ? + ( n + 1 ) M ? ∑ j = 0 M ? 1 ∑ i = 0 n [ i < = ? j c + c ? ( b m o d     c ) ? 1 a m o d     c ? = S n 1 ? a c ? + S n 0 ? b c ? + ( n + 1 ) M ? F ( c , c ? ( b m o d     c ) ? 1 , a m o d     c , M ? 1 ) ? M = S n 1 ? a c ? + S n 0 ? b c ? + n M ? F ( c , c ? ( b m o d     c ) ? 1 , a m o d     c , M ? 1 ) F(a,b,c,n) = S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + \sum_{i=0}^n \lfloor\frac {(a\mod c)i+(b\mod c)}c\rfloor\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + \sum_{j=0}^{M-1} \sum_{i=0}^n[j< \lfloor\frac {(a\mod c)i+(b\mod c)}c\rfloor]\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + \sum_{j=0}^{M-1} \sum_{i=0}^n1-[j> = \lfloor\frac {(a\mod c)i+(b\mod c)}c\rfloor]\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + (n+1)M-\sum_{j=0}^{M-1} \sum_{i=0}^n[j+1> \lfloor\frac {(a\mod c)i+(b\mod c)}c\rfloor]\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + (n+1)M-\sum_{j=0}^{M-1} \sum_{i=0}^n[i(a\mod c)< (j+1)c-(b\mod c)]\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + (n+1)M-\sum_{j=0}^{M-1} \sum_{i=0}^n[i(a\mod c)< =(j+1)c-(b\mod c)-1]\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + (n+1)M-\sum_{j=0}^{M-1} \sum_{i=0}^n[i< =\lfloor\frac {(j+1)c-(b\mod c)-1}{a\mod c}\rfloor]\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + (n+1)M-\sum_{j=0}^{M-1} \sum_{i=0}^n[i< =\lfloor\frac {jc+c-(b\mod c)-1}{a\mod c}\rfloor\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + (n+1)M-F(c,c-(b\mod c)-1,a\mod c,M-1)-M\\ =S_n^1\lfloor\frac ac\rfloor + S_n^0\lfloor \frac bc\rfloor + nM-F(c,c-(b\mod c)-1,a\mod c,M-1) F(a,b,c,n)=Sn1??ca??+Sn0??cb??+i=0∑n??c(amodc)i+(bmodc)??=Sn1??ca??+Sn0??cb??+j=0∑M?1?i=0∑n?[j=?c(amodc)i+(bmodc)??]=Sn1??ca??+Sn0??cb??+(n+1)M?j=0∑M?1?i=0∑n?[j+1>?c(amodc)i+(bmodc)??]=Sn1??ca??+Sn0??cb??+(n+1)M?j=0∑M?1?i=0∑n?[i(amodc)<(j+1)c?(bmodc)]=Sn1??ca??+Sn0??cb??+(n+1)M?j=0∑M?1?i=0∑n?[i(amodc)<=(j+1)c?(bmodc)?1]=Sn1??ca??+Sn0??cb??+(n+1)M?j=0∑M?1?i=0∑n?[i<=?amodc(j+1)c?(bmodc)?1??]=Sn1??ca??+Sn0??cb??+(n+1)M?j=0∑M?1?i=0∑n?[i<=?amodcjc+c?(bmodc)?1??=Sn1??ca??+Sn0??cb??+(n+1)M?F(c,c?(bmodc)?1,amodc,M?1)?M=Sn1??ca??+Sn0??cb??+nM?F(c,c?(bmodc)?1,amodc,M?1)
高斯函数与整数大于小于号化简技巧：
x < a x< a xa b < x ab< x aba b < = x ab< =x ab<=x即 a < = ? x b ? a< =\lfloor \frac xb\rfloor a<=?bx??
a b < x ab< x ab 这样也比较好反着推回去。
整除函数推式子，和数论函数推式子差不多恶心吧，
杜教洲阁，欧几里得。
例题：
求 ∑ k = 0 n ( ( k m )a n dm ) ( m o d 1 e 9 + 7 ) \sum_{k=0}^n ((km)\ and \ m)\pmod {1e9+7} ∑k=0n?((km) and m)(mod1e9+7)
其中 a n d and and为按位与, m < = 1 e 11 , n < = 1 e 18 m< =1e11,n< =1e18 m<=1e11,n<=1e18
按位计算，求有多少个 k k k使得 ( k m )a n dm (km)\ and \ m (km) and m在第 i i i位为1.
那么这个可以转化为等差数列除 2 i 2^i 2i之和，
就是经典的类欧几里得算法了。
【模板|类欧几里得算法】AC Code:

#include #define maxn 100005 #define mod 1000000007 #define LL long long using namespace std; int F(LL a,LL b,LL c,LL n){ int N = n % mod; LL m = ((__int128)(a % c) * n + (b % c)) / c; LL ret = (1ll * N * (N+1) / 2 % mod * (a / c % mod) + 1ll * (N+1) * (b / c % mod)) % mod; if(a % c == 0) return ret; return (ret + 1ll * N * (m % mod) - F(c,c-(b%c)-1,a%c,m-1)) % mod; } LL n,m; int main(){ scanf("%lld%lld",&n,&m); int ans = 0; for(int i=0; i<=60; i++) if(m>>i&1){ int c = (F(m,0,1ll<