类欧几里得算法|bzoj3817: Sum【类欧几里得算法】

题目大意: 给出 T≤1e4T ≤ 1 e 4 组询问,对于每组询问,给定 n≤1e9,R≤1e4n ≤ 1 e 9 , R ≤ 1 e 4 ,求:

∑i=1n(?1)?iR√?∑ i = 1 n ( ? 1 ) ? i R ?
解题思路: 设 r=R??√r = R ,则 ?ir?? i r ? 为奇数时为-1,为偶数时为1,又有:

?x??2?x2?=???1,?x?%2=10,?x?%2=0? x ? ? 2 ? x 2 ? = { 1 , ? x ? % 2 = 1 0 , ? x ? % 2 = 0
所以:

ans=∑i=1n(1?2(?ir??2?ir2?))=n?2∑i=1n?ir?+4∑i=1n?ir2?a n s = ∑ i = 1 n ( 1 ? 2 ( ? i r ? ? 2 ? i r 2 ? ) ) = n ? 2 ∑ i = 1 n ? i r ? + 4 ∑ i = 1 n ? i r 2 ?
那么如何求形如 f(k,n)=∑i=1n?ki?f ( k , n ) = ∑ i = 1 n ? k i ? 呢?
还是用类欧几里得的方法:
当 k≥1,f(k,n)=f(k??k?,n)+?k?n(n+1)/2k ≥ 1 , f ( k , n ) = f ( k ? ? k ? , n ) + ? k ? n ( n + 1 ) / 2
当 k<1k < 1 , f(k,n)=∑i=1n∑j=1m[ki≥j],m=?kn?f ( k , n ) = ∑ i = 1 n ∑ j = 1 m [ k i ≥ j ] , m = ? k n ?
注意这里与普通类欧的不同,这里 kk 是小数,所以 ki≥jk i ≥ j 并不等价于 ki>j?1k i > j ? 1 ,但当 j/kj / k 不是整数时等价于 i>?j/k?i > ? j / k ? ,所以当 rr 为整数时我们直接计算,只讨论 rr 为无理数的情况:
f(k,n)=∑i=1n∑j=1m[i>?j/k?]f ( k , n ) = ∑ i = 1 n ∑ j = 1 m [ i > ? j / k ? ]
f(k,n)=∑j=1m(n??j/k?)f ( k , n ) = ∑ j = 1 m ( n ? ? j / k ? )
f(k,n)=nm?f(1k,m)f ( k , n ) = n m ? f ( 1 k , m )
一直递归,当 n=0n = 0 时返回0,复杂度据说是 O(log)O ( l o g ) 的,但我并不会证……
(就是 n=kn,k=1k?1n = k n , k = 1 k ? 1 一直递归的复杂度)
注意不能斜率不能用double,会卡精,要用 k=ar+bck = a r + b c 的形式维护整形三元组 (a,b,c)( a , b , c ) 才行,就两个操作,取小数部分和取倒数:
取小数: ar+bc?k=ar+b?kcc,k=?ar+bc?a r + b c ? k = a r + b ? k c c , k = ? a r + b c ?
取倒数: car+b=c(ar?b)(ar+b)(ar?b)=acr?bca2R?b2c a r + b = c ( a r ? b ) ( a r + b ) ( a r ? b ) = a c r ? b c a 2 R ? b 2
【类欧几里得算法|bzoj3817: Sum【类欧几里得算法】】迭代即可。

#include #define ll long long using namespace std; int getint() { int i=0,f=1; char c; for(c=getchar(); c!='-'&&(c<'0'||c>'9'); c=getchar()); if(c=='-')f=-1,c=getchar(); for(; c>='0'&&c<='9'; c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; } ll n,R; double r; ll gcd(ll a,ll b){return b?gcd(b,a%b):a; } ll f(ll a,ll b,ll c,ll n) { if(!n)return 0; ll g=gcd(a,gcd(b,c)); a/=g,b/=g,c/=g; ll tmp=(a*r+b)/c; b-=tmp*c,tmp*=n*(n+1)/2; ll m=(a*r+b)*n/c; return m*n+tmp-f(a*c,-b*c,a*a*R-b*b,m); } int main() { //freopen("lx.in","r",stdin); for(int T=getint(); T; T--) { n=getint(),R=getint(),r=sqrt(R); int x=r; if(x*x==R)printf("%d\n",(x&1)?((n&1)?-1:0):n); else printf("%d\n",n-2*f(1,0,1,n)+4*f(1,0,2,n)); } return 0; }

    推荐阅读