bzoj 3817: Sum 类欧几里得算法 bzoj

这道题目solution写了两种做法，都讲一下吧。
首先，令x=r^0.5，显然，如果x>2，则可以不断减2到小于二；如果x>1，那么变为2-x。因此此时必有x<1。（特判r为完全平方数的情况）。那么令y=1/x，则：
题目等价于在数轴从0~n，以y长度为一个区间（左闭右开）黑白交替染色，求黑色部分覆盖的整点减去白色部分覆盖的整点。然后把最后面零散的部分暴力计算，如果最后一个是黑色的也暴力计算。那么这个时候黑白段数相等，且每一段黑（白）都至少覆盖[y]个点恰好各自抵消[y]，那么将每一段都去掉[y]的长度，则n’={y}/y*n，y'={y}继续计算。显然y>1则y>1+{y}>2{y}，因此为logN。
另一种为类欧几里得算法。感觉这一种比较有用就用了这一种，如下：
欧几里得算法：计算gcd(x,y)，可以由gcd(y,x%y)得到。类欧几里得算法同理。
令x=r^0.5，显然，(-1)^[d*x]为=1+2*(2[d*x/2]-[d*x])，那么相当于求：
n+4*Σ(d=1,n)[d*x/2]-2*Σ(d=1,n)[d*x]，来看一般形式即求Σ(i=1,n) [(bx+c)/a*i]
如果[(bx+c)/a]>=1，那么显然可以把整数部分先单独求出来；那么不妨令k=(bx+c)/a<1，则题目相当于求线段y=kx(0 bzoj 3817: Sum 类欧几里得算法
文章图片

上图中就是A~G,B~F,C~E和D（还有D左边那个QAQ作图的时候没注意）。注意原本我们是枚举横坐标i然后下取整，但是当k<1的时候显然纵坐标的范围小于横坐标，因此我们枚举纵坐标j，那么有j<=[kn]，然后由相似得到直线y=j上的整点个数为[(kn-j)/k]+1=n-[j/k]，那么实际上就是求出Σ(j=1,[kn]) [j/k]，可以递归处理。这样就是O(logN)的。为了避免爆int(long long)，需要每次递归的时候约分，因此为O(log^2N)，另外1/k需要分母有理化。可以发现这就是一个直角三角形不断压缩翻转的过程。
AC代码如下：

#include #include #include #include using namespace std; int n,m; double t; int read(){ int x=0; char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x; } int gcd(int x,int y){ return (y)?gcd(y,x%y):x; } int solve(int n,int a,int b,int c){ if (!n) return 0; int tmp=gcd(gcd(a,b),c); a/=tmp; b/=tmp; c/=tmp; tmp=(t*b+c)/a; int sum=1ll*n*(n+1)*tmp>>1; c-=tmp*a; tmp=(t*b+c)/a*n; return sum+n*tmp-solve(tmp,b*b*m-c*c,a*b,-a*c); } int main(){ int cas=read(); while (cas--){ n=read(); m=read(); t=sqrt(m); if ((int)t==t) printf("%d\n",(m&1)?((n&1)?-1:0):n); else printf("%d\n",n+(((solve(n,2,1,0)<<1)-solve(n,1,1,0))<<1)); } return 0; }

by lych
【bzoj 3817: Sum 类欧几里得算法】2016.5.8