首页 > 考试 > 其他 > 正文
[BZOJ3817][类欧几里得算法]Sum
2017-03-14       个评论    来源:CE玩家  
收藏    我要投稿

[BZOJ3817][类欧几里得算法]Sum

题意


给定N,R
∑nd=1(?1)?d2R?


类欧算法裸题

#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",n);
            else if(n&1) printf("%d\n",-1);
            else printf("%d\n",0);
        else printf("%d\n",n+4*solve(n,2,1,0)-2*solve(n,1,1,0));
    }
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:[BZOJ2712][Violet 2][类欧几里得算法]棒球
下一篇:leetcode 第28题( Implement strStr())(java)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站