题目大意： 给出 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;
}
推荐阅读
- bzoj|Bzoj3817:Sum
- BZOJ|BZOJ2763[JLOI2011]飞行路线【分层图最短路】
- Bzoj|[BZOJ2187][fraction][类欧几里得算法]
- 类欧几里得算法|[BZOJ2712][[Violet 2]棒球][类欧几里得算法]
- 2017|[BZOJ3817][Sum][类欧几里得算法 数论]
- 凸包|bzoj5317: [Jsoi2018]部落战争【凸包/Minkowski sum】
- 数论|BZOJ 3560 DZY Loves Math V 数论
- online|bzoj2286: [Sdoi2011消耗战
- bzoj 3817: Sum 类欧几里得算法