[BZOJ 3817][クラスユークリッドアルゴリズム]Sum

題意
Nが与えられていると、RはΣnd=1（−1）⌊d2 R⌋を求める。
クラスの欧のアルゴリズムの裸問題はこれを見ることができます。http://blog.csdn.net/lych_cys/articale/detail/51345089

#include 
#include 
#include 
#include 

using namespace std;

int n,r,T;
double t;

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

int solve(int n,int a,int b,int c){
    if(n<=0) return 0;
    int d=gcd(gcd(a,b),c); a/=d; b/=d; c/=d;
    int tmp=(b*t+c)/a,sum=1ll*tmp*n*(n+1)>>1;
    c-=tmp*a; tmp=(b*t+c)/a*n;
    return sum+n*tmp-solve(tmp,b*b*r-c*c,a*b,-a*c);
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&r); t=sqrt(1.0*r);
        if((int)t==t)
            if((r&1)^1) printf("%d
",n);
            else if(n&1) printf("%d
",-1);
            else printf("%d
",0);
        else printf("%d
",n+4*solve(n,2,1,0)-2*solve(n,1,1,0));
    }
    return 0;
}