c/c++语言开发共享[P5172] Sum

のすたの“类欧几里得算法”第一题 sum

【题意】

给入(n,r)，求(sum_{d=1}^n(-1)^{lfloor dsqrt r rfloor})。

【分析】

只需要考虑所有(d)中，(lfloor dsqrt rrfloor)为偶数的个数。显然(lfloor xrfloor)为偶数(leftrightarrow lfloor xrfloor=2timeslfloorfrac{x}{2}rfloor)。 那么原式可以改写为：
[ sum_{d=1}^n 1-2times(lfloor dsqrt rrfloorbmod 2)=sum_{d=1}^n 1-2times(lfloor dsqrt rrfloor-2timeslfloorfrac{dsqrt r}{2}rfloor)\ =n-2timessum_{d=1}^nlfloor dsqrt rrfloor+4timessum_{d=1}^nlfloorfrac{dsqrt r}{2}rfloor ]
不妨设(f(a,b,c,n)=sum_{d=1}^nlfloor dtimesfrac{asqrt r+b}{c}rfloor)，那么原式即为
[ n-2times f(1,0,1,n)+4times f(1,0,2,n) ]
考虑关于(f(a,b,c,n))的算法，（开始扣题了），设(k=frac{asqrt r +b}{c})。

当(kge1)时，(k)可以拆为一个正数+小于1的非负实数，即
[ f(a,b,c,n)=sum_{d=1}^n lfloor dtimes krfloor=sum_{d=1}^n dtimeslfloor krfloor+lfloor dtimes(k-lfloor krfloor)rfloor\ =frac{n(n+1)}{2}lfloor krfloor+sum_{d=1}^nlfloor dtimesfrac{asqrt r+b-lfloor krfloortimes c}{c}rfloor\ =frac{n(n+1)}{2}lfloor krfloor+f(a,b-lfloor krfloortimes c,c,n) ]
当(k<1)时，（比如上面递归的那层），可以看作是满足
[ begin{cases} 0<xle n\ 0<yle xtimes k\ xin z\ yin z end{cases} ]
的点数。考虑再矩形((1,1)(n,lfloor ntimes krfloor))内容斥可得个数为(ntimeslfloor ntimes krfloor) 减去左上三角的部分，而那部分可当作是(y=xtimes k, xin[1,n])的反函数(y=xtimes dfrac{1}{k}, xin[1,lfloor ntimes krfloor])。

其中(dfrac{1}{k}=dfrac{c}{asqrt r+b}=dfrac{c(asqrt r-b)}{(asqrt r+b)(asqrt r-b)}=dfrac{acsqrt r-bc}{a^2r-b^2})。
[ f(a,b,c,n)=ntimeslfloor ntimes krfloor-f(ac,-bc,a^2r-b^2,lfloor ntimes krfloor) ]
可以发现，情况一二交替递归，且每轮的总的变化与欧几里得算法相似，故知其复杂度为(log​)级的。

难度海星。。

然而当(r)为完全平方数时需要单独算，大概会爆ll吧。。

#include <bits/stdc++.h> #define ll long long using namespace std; ll n,r; double x; ll f(ll a,ll b,ll c,ll n) {     if(!n) return 0;     ll d=__gcd(__gcd(a,b),c);     a/=d, b/=d, c/=d;     double k=(a*x+b)/c;     if(k>=1) return n*(n+1)/2*(ll)(k)+f(a,b-(ll)(k)*c,c,n);     else return n*(ll)(n*k)-f(a*c,-b*c,a*a*r-b*b,(ll)(n*k)); } int main() {     int t;     scanf("%d",&t);     while(t--) {         scanf("%lld%lld",&n,&r);         x=sqrt(r);         ll c=x;         if(c*c==r) {             if(c&1) printf("%lldn",n-2*((n+1)/2));             else printf("%lldn",n);         }          else printf("%lldn",n-2*f(1,0,1,n)+4*f(1,0,2,n));     }     return 0; }