类欧几里得算法总结

定义

$$f(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor$$

$$g(a,b,c,n)=\sum_{i=0}^ni\lfloor {ai+b \over c} \rfloor$$

$$h(a,b,c,n)=\sum_{i=0}^n\lfloor {ai+b \over c} \rfloor^2$$

f

$$f(a,b,c,n)={a\over c}\times n \times {n+1 \over 2} +{b \over c} \times (n+1)+f(a \%c,b\%c,c,n)$$

$$f(a,b,c,n)=\sum_{i=0}^n\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[ai \geq cj+c-b]$$

$$=\sum_{i=0}^n\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

$$=\sum_{j=0}^{m}(n-{cj+c-b-1 \over a})$$

$$=m\times n-\sum_{j=0}^{m}{cj+c-b-1 \over a}$$

$$f(a,b,c,n)=m\times n-f(c,c-b-1,a,m-1)$$

$$f(a,b,c,n)={an+b \over c}\times n-f(c,c-b-1,a,{an+b \over c}-1)$$

g

$$g(a,b,c,n)={a\over c}\times n \times (n+1)\times {2n+1 \over 6}+{b\over c}\times n\times {n+1\over 2}+g(a\%c,b\%c,c,n)$$

$a$和$b$都小于$c$和上面一样推

$$g(a,b,c,n)=\sum_{i=0}^ni\sum_{j=0}^{m-1}[{ai+b \over c} \geq j+1]$$

$$=\sum_{i=0}^ni\sum_{j=0}^{m-1}[i>{cj+c-b-1 \over a}]$$

$$={1\over2}\sum_{j=0}^{m-1}(n+1+{cj+c-b-1 \over a})\times(n-{cj+c-b-1 \over a})$$

$$={1\over2}\sum_{j=0}^{m-1}n\times (n+1)-{cj+c-b-1 \over a}+({cj+c-b-1 \over a})^2$$

$$g(a,b,c,n)={1 \over 2}[(n+1)\times n\times m-f(c,c-b-1,a,m-1)-g(c,c-b-1,a,m-1) ]$$

h

$$h(a,b,c,n)=({a\over c})^2\times {n(n+1)(2n+1)\over 6}+({b\over c})^2\times(n+1)+{a\over c}\times{b\over c}\times n(n+1)+h(a\%c,b\%c,c,n)+2\times {a\over c}\times g(a\%c,b\%c,c,n)+2\times {b\over c}\times f(a\%c,b\%c,c,n)$$

$$n^2=2\times \frac{n(n+1)}{2}-n=2\sum_{i=0}^ni-n$$

$$h(a,b,c,n)=\sum_{i=0}^n(2\times \sum_{j=1}^{(ai+b)/c}j-{ai+b\over c})$$

$$=2\times \sum_{j=0}^{m-1}(j+1)\times\sum_{i=0}^n[{ai+b \over c} \geq j+1]-f(a,b,c,n)$$

$$h(a,b,c,n)=2\times \sum_{j=0}^{m-1}(j+1)*(n-{cj+c-b-1 \over a})-f(a,b,c,n)$$

$$h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)$$

例题 bzoj 3817

题意

$$\large \sum_{d=1}^{n} (-1)^{\lfloor \sqrt{d\times r\times d} \rfloor}$$

题解

\begin{align} -1^{dx } & =1-2( dx \% 2) \\ &=1-2(dx – \frac{dx}{2} * 2) \\ &= 1+4\frac{dx}{2} + 2 dx \end{align}

$$原式 =n + 4 \sum_{d=1}^{n} \frac{dx}{2}-2\sum_{d=1}^{n}dx$$

#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
double t;
ll m,n;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll calc(ll n,ll a,ll b,ll c)
{
if (!n) return 0ll;
ll g=gcd(a,gcd(b,c));
a/=g,b/=g,c/=g;
ll k=(t*b+c)/a,ans=n*(n+1)/2*k;
c-=k*a,k=(t*b+c)/a*n;
ans+=n*k,ans-=calc(k,b*b*m-c*c,a*b,-a*c);
return ans;
}
main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&m),t=sqrt(m);
if ((ll)t==t)
printf("%lld\n",(ll)(m&1)?((n&1)?-1:0):n);
else
printf("%lld\n",n+(calc(n,2,1,0)<<2)-(calc(n,1,1,0)<<1));
}

}