BZOJ3817 Sum（类欧几里得算法）

设$t=\sqrt r$，原题转化为$\sum_{x=1}^n(4*\lfloor\frac{tx}2\rfloor-2*\lfloor tx\rfloor+1)$
考虑如何求$\sum_{x=1}^n\lfloor\frac{bt+c}ax\rfloor$
开始我写了一个真欧几里得来求直线下整点数目，然后由于里头含小数所以不对。
于是学习了一下新姿势，思想其实差不多。
先把a,b,c同时除以gcd(a,b,c)，防止爆int。
之后把斜率变成$\frac{bt+c}a-\lfloor\frac{bt+c}a\rfloor$，并计算对应贡献。
第三步把x,y轴互换，这时斜率变成了倒数，即$\frac a{bt+c}=\frac {abt-ac}{b^2t^2-c^2}$
特判r是完全平方数的时刻，因为这样直线上会有点，所以减的时候会减多。
补充：真欧几里得算法：
$$\sum_{0<=x<n} \lfloor \frac{ax+b}{c} \rfloor=n*\lfloor \frac{b}{c} \rfloor+\frac{n*(n-1)}{2}*\lfloor \frac{a}{c} \rfloor+\sum_{0<=x<\lfloor \frac{(a\%c)*n+b\%c\quad}{c} \rfloor} \lfloor \frac{cx+(an+b)\%c}{a\%c} \rfloor$$

#include <cstdio>

#include <cmath>

int T,n,r;

double t;

int gcd(int a,int b) {return b?gcd(b,a%b):a;}

int sol(int n,int a,int b,int c) {

    if (!n) return ;

    int tmp=gcd(gcd(a,b),c); a/=tmp; b/=tmp; c/=tmp;

    tmp=(t*b+c)/a; int sum=1ll*n*(n+)*tmp>>;

    c-=tmp*a; tmp=(t*b+c)*n/a;

    return sum+n*tmp-sol(tmp,b*b*r-c*c,a*b,-a*c);

}

int main() {

    scanf("%d",&T);

    while(T--) {

        scanf("%d%d",&n,&r),t=sqrt(r);

        if((int)t==t) printf("%d\n",(r&)?((n&)?-:):n);

        else printf("%d\n",n+*sol(n,,,)-*sol(n,,,));

    }

    return ;

}

巴特西

BZOJ3817 Sum（类欧几里得算法）

最新文章

热门文章