锐客网

  1. 首页 > it技术 > >

题解|[BZOJ3817] Sum

题解---数论

Description 【题解|[BZOJ3817] Sum】给出n,r
求
∑i=1n(?1)?ir√?∑ i = 1 n ( ? 1 ) ? i r ?
T组数据
T,r<=10000,n<=10^9
Solution 转化式子
(?1)a=1?2×(amod2)( ? 1 ) a = 1 ? 2 × ( a mod 2 )
amod2=a?2×?a/2?a mod 2 = a ? 2 × ? a / 2 ?
原式化为 n?2∑i=1n?ir√?+4∑i=1n?ir√2?n ? 2 ∑ i = 1 n ? i r ? + 4 ∑ i = 1 n ? i r 2 ?
如果r是完全平方数就可以直接计算
考虑如何计算 ∑i=1n?ir√?∑ i = 1 n ? i r ?
即求一个斜率为无理数的正比例函数下整点个数
令 t=r√t = r
将 ?ir√?? i r ? 表示成 ?i×at+bc?? i × a t + b c ? 的形式,a,b,c都是整数，一开始a=1,b=0,c=1
现在考虑如何计算 ∑i=1n?i×at+bc?∑ i = 1 n ? i × a t + b c ?
当 at+bc≥1a t + b c ≥ 1
?i×at+bc?=?i×(at+bc??at+bc?)?+i×?at+bc?? i × a t + b c ? = ? i × ( a t + b c ? ? a t + b c ? ) ? + i × ? a t + b c ?
后面这部分可以直接计算出，前面就更新b，继续递归处理
当 0 既然要求的是一个原点为顶点的直角三角形中整点个数，且斜率小于1，邻边长为n
题解|[BZOJ3817] Sum
文章图片

我们可以将x,y轴互换（关于直线y=x对称）
题解|[BZOJ3817] Sum
文章图片

那么就变成了求上方白色三角形中整点个数，它与红色三角形中整点个数是一样的
这时对边变成了n，而邻边变成了 ?n×at+bc?? n × a t + b c ?
把这个看成是新的n
同时斜率变为原来的倒数，即 cat+bc a t + b
分母有理化
cat+b=act?bca2r?b2c a t + b = a c t ? b c a 2 r ? b 2
又得出了新的a,b,c递归处理
注意有可能会爆Long long 分式需要上下同除gcd(a,b,c)
似乎这个过程很像类欧几里得算法
复杂度分析:
设 k=at+bck = a t + b c
可以发现上面的过程是轮流交替的
如果 12 那么k大于1/2时减小速度至少是1/2的
如果 k<12k < 1 2 ，那么n的减小速度又至少是1/2了
因此总的复杂度是 O(logN)O ( log ? N ) 的
好像r如果是完全平方数就会算重来着。。。因此要放在之前特殊计算
Code

#include #include #include #include #include #include #define fo(i,a,b) for(int i=a; i<=b; i++) #define fod(i,a,b) for(int i=a; i>=b; i--) #define LL long long using namespace std; LL n,r; double q; LL gcd(LL x,LL y) { return(!y)?x:gcd(y,x%y); } LL calc(LL a,LL b,LL c,LL n) { if(n==0) return 0; if(n==1) return (LL)(a*q+b)/c; LL v=gcd(gcd(a,b),c); a/=v,b/=v,c/=v; LL p=(a*q+b)/c,s=0; if(p==0) { LL n1=((a*q+b)/c*n); return (n1*n-calc(a*c,-b*c,a*a*r-b*b,(LL)n1)); } else { return p*(n*(LL)(n+1)/2)+calc(a,b-c*p,c,n); } } int main() { int t; cin>>t; while(t--) { scanf("%lld%lld",&n,&r); q=sqrt(r); int t=(int)q; if(t*t==r) { if(t%2==0) printf("%lld\n",n); else printf("%lld\n",n-2*((n+1)/2)); } else { printf("%lld\n",n-(LL)2*calc(1,0,1,n)+(LL)4*calc(1,0,2,n)); } } }

    推荐阅读


    上一篇：动态规划|Longest Common Subsequence（入门dp题）

    下一篇：android反编译-smali语法