给定 n , r n,r n , r ∑ d = 1 n ( − 1 ) ⌊ d r ⌋ \sum\limits_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor} d = 1 ∑ n ( − 1 ) ⌊ d r ⌋
Sol 3
先考虑一个经典结论：
( − 1 ) x = 1 − 2 [ x m o d 2 = 1 ] (-1)^x=1-2[x\bmod 2=1] ( − 1 ) x = 1 − 2 [ x mod 2 = 1 ] 然后考虑从这个结论入手来获取一些有用的信息：
( − 1 ) x = 1 − 2 [ x m o d 2 = 1 ] = 1 − 2 ( x − 2 ⌊ x 2 ⌋ ) = 1 − 2 x + 4 ⌊ x 2 ⌋ \begin{aligned}
&(-1)^x\\
=&1-2[x\bmod 2=1]\\
=&1-2(x-2\lfloor\frac x2\rfloor)\\
=&1-2x+4\lfloor\frac x2\rfloor
\end{aligned} = = = ( − 1 ) x 1 − 2 [ x mod 2 = 1 ] 1 − 2 ( x − 2 ⌊ 2 x ⌋) 1 − 2 x + 4 ⌊ 2 x ⌋ 然后考虑把这个东西带入原式：
∑ d = 1 n ( − 1 ) ⌊ d r ⌋ = ∑ d = 1 n ( 1 − 2 ⌊ d r ⌋ + 4 ⌊ ⌊ d r ⌋ 2 ⌋ ) = ( ∑ d = 1 n 1 ) − ( ∑ d = 1 n 2 ⌊ d r ⌋ ) + ( ∑ d = 1 n 4 ⌊ ⌊ d r ⌋ 2 ⌋ ) = n − ( ∑ d = 1 n 2 ⌊ d r ⌋ ) + ( ∑ d = 1 n 4 ⌊ d r 2 ⌋ ) \begin{aligned}
&\sum\limits_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor}\\
=&\sum\limits_{d=1}^n(1-2\lfloor d\sqrt r\rfloor+4\lfloor\frac{\lfloor d\sqrt r\rfloor}2\rfloor)\\
=&(\sum\limits_{d=1}^n1)-(\sum\limits_{d=1}^n2\lfloor d\sqrt r\rfloor)+(\sum\limits_{d=1}^n4\lfloor\frac{\lfloor d\sqrt r\rfloor}2\rfloor)\\
=&n-(\sum\limits_{d=1}^n2\lfloor d\sqrt r\rfloor)+(\sum\limits_{d=1}^n4\lfloor\frac{d\sqrt r}2\rfloor)\\
\end{aligned} = = = d = 1 ∑ n ( − 1 ) ⌊ d r ⌋ d = 1 ∑ n ( 1 − 2 ⌊ d r ⌋ + 4 ⌊ 2 ⌊ d r ⌋ ⌋) ( d = 1 ∑ n 1 ) − ( d = 1 ∑ n 2 ⌊ d r ⌋) + ( d = 1 ∑ n 4 ⌊ 2 ⌊ d r ⌋ ⌋) n − ( d = 1 ∑ n 2 ⌊ d r ⌋) + ( d = 1 ∑ n 4 ⌊ 2 d r ⌋) 考虑换元，令 x = r x=\sqrt r x = r γ ( a , b , c , n ) = ∑ i = 1 n ⌊ a x + b c × i ⌋ \gamma(a,b,c,n)=\sum\limits_{i=1}^n\lfloor\frac{ax+b}c\times i\rfloor γ ( a , b , c , n ) = i = 1 ∑ n ⌊ c a x + b × i ⌋ n − 2 γ ( 1 , 0 , 1 , n ) + 4 γ ( 1 , 0 , 2 , n ) n-2\gamma(1,0,1,n)+4\gamma(1,0,2,n) n − 2 γ ( 1 , 0 , 1 , n ) + 4 γ ( 1 , 0 , 2 , n ) γ \gamma γ
这里注意到 a x + b c \frac{ax+b}c c a x + b
1. a x + b c = 1 \large\frac{ax+b}c=1 c a x + b = 1
此时有 γ ( a , b , c , n ) = ∑ i = 1 n 1 = n \gamma(a,b,c,n)=\sum\limits_{i=1}^n 1=n γ ( a , b , c , n ) = i = 1 ∑ n 1 = n
2. a x + b c > 1 \large\frac{ax+b}c>1 c a x + b > 1
记 t = a x + b c , T = ⌊ t ⌋ t=\frac{ax+b}c,T=\lfloor t\rfloor t = c a x + b , T = ⌊ t ⌋
γ ( a , b , c , n ) = ∑ i = 1 n ⌊ t i ⌋ = ∑ i = 1 n ⌊ t i − T i + T i ⌋ = ∑ i = 1 n ⌊ t i − T i ⌋ + ∑ i = 1 n T i = ∑ i = 1 n ⌊ ( a x + b c − T ) i ⌋ + n ( n + 1 ) T 2 = γ ( a , b − c T , c , n ) + n ( n + 1 ) T 2 \begin{aligned}
&\gamma(a,b,c,n)\\
=&\sum\limits_{i=1}^n\lfloor ti\rfloor\\
=&\sum\limits_{i=1}^n\lfloor ti-Ti+Ti\rfloor\\
=&\sum\limits_{i=1}^n\lfloor ti-Ti\rfloor+\sum\limits_{i=1}^nTi\\
=&\sum\limits_{i=1}^n\lfloor(\frac{ax+b}c-T)i\rfloor+\frac{n(n+1)T}2\\
=&\gamma(a,b-cT,c,n)+\frac{n(n+1)T}2
\end{aligned} = = = = = γ ( a , b , c , n ) i = 1 ∑ n ⌊ t i ⌋ i = 1 ∑ n ⌊ t i − T i + T i ⌋ i = 1 ∑ n ⌊ t i − T i ⌋ + i = 1 ∑ n T i i = 1 ∑ n ⌊( c a x + b − T ) i ⌋ + 2 n ( n + 1 ) T γ ( a , b − c T , c , n ) + 2 n ( n + 1 ) T 3. a x + b c < 1 \large\frac{ax+b}c<1 c a x + b < 1
此时有 T = 0 T=0 T = 0
γ ( a , b , c , n ) = ∑ i = 1 n ⌊ t i ⌋ = ∑ i = 1 n ∑ j = 1 ⌊ n t ⌋ [ j < t i ] = ∑ i = 1 n ∑ j = 1 ⌊ n t ⌋ [ i > j t ] = ∑ j = 1 ⌊ n t ⌋ ∑ i = 1 n [ i > j t ] = ∑ j = 1 ⌊ n t ⌋ ( n − ⌊ j t ⌋ ) = ∑ j = 1 ⌊ n t ⌋ ( n − ⌊ j a x + b c ⌋ ) = ∑ j = 1 ⌊ n t ⌋ ( n − ⌊ j c a x + b ⌋ ) = n ⌊ n t ⌋ − ∑ j = 1 ⌊ n t ⌋ ⌊ c a x + b j ⌋ = n ⌊ n t ⌋ − ∑ j = 1 ⌊ n t ⌋ ⌊ c ( a x − b ) a 2 x 2 − b 2 j ⌋ = n ⌊ n t ⌋ − ∑ j = 1 ⌊ n t ⌋ ⌊ c a x − c b a 2 r − b 2 j ⌋ = n ⌊ n t ⌋ − γ ( c a , − c b , a 2 r − b 2 , ⌊ n t ⌋ ) \begin{aligned}
&\gamma(a,b,c,n)\\
=&\sum\limits_{i=1}^n\lfloor ti\rfloor\\
=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor nt\rfloor}[j<ti]\\
=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor nt\rfloor}[i>\frac jt]\\
=&\sum\limits_{j=1}^{\lfloor nt\rfloor}\sum\limits_{i=1}^n[i>\frac jt]\\
=&\sum\limits_{j=1}^{\lfloor nt\rfloor}(n-\lfloor \frac jt\rfloor)\\
=&\sum\limits_{j=1}^{\lfloor nt\rfloor}\left(n-\left\lfloor\frac j{\frac{ax+b}c}\right\rfloor \right)\\
=&\sum\limits_{j=1}^{\lfloor nt\rfloor}\left(n-\left\lfloor\frac{jc}{ax+b}\right\rfloor \right)\\
=&n\lfloor nt\rfloor-\sum\limits_{j=1}^{\lfloor nt\rfloor}\left\lfloor\frac{c}{ax+b}j\right\rfloor\\
=&n\lfloor nt\rfloor-\sum\limits_{j=1}^{\lfloor nt\rfloor}\left\lfloor\frac{c(ax-b)}{a^2x^2-b^2}j\right\rfloor\\
=&n\lfloor nt\rfloor-\sum\limits_{j=1}^{\lfloor nt\rfloor}\left\lfloor\frac{cax-cb}{a^2r-b^2}j\right\rfloor\\
=&n\lfloor nt\rfloor-\gamma(ca,-cb,a^2r-b^2,\lfloor nt\rfloor)
\end{aligned} = = = = = = = = = = = γ ( a , b , c , n ) i = 1 ∑ n ⌊ t i ⌋ i = 1 ∑ n j = 1 ∑ ⌊ n t ⌋ [ j < t i ] i = 1 ∑ n j = 1 ∑ ⌊ n t ⌋ [ i > t j ] j = 1 ∑ ⌊ n t ⌋ i = 1 ∑ n [ i > t j ] j = 1 ∑ ⌊ n t ⌋ ( n − ⌊ t j ⌋) j = 1 ∑ ⌊ n t ⌋ ( n − ⌊ c a x + b j ⌋ ) j = 1 ∑ ⌊ n t ⌋ ( n − ⌊ a x + b j c ⌋ ) n ⌊ n t ⌋ − j = 1 ∑ ⌊ n t ⌋ ⌊ a x + b c j ⌋ n ⌊ n t ⌋ − j = 1 ∑ ⌊ n t ⌋ ⌊ a 2 x 2 − b 2 c ( a x − b ) j ⌋ n ⌊ n t ⌋ − j = 1 ∑ ⌊ n t ⌋ ⌊ a 2 r − b 2 c a x − c b j ⌋ n ⌊ n t ⌋ − γ ( c a , − c b , a 2 r − b 2 , ⌊ n t ⌋) 同样也得到了递归公式。简单分析可知该算法时间复杂度同样为 O ( log n ) O(\log n) O ( log n )
corner case
需要特殊处理 r ∈ N \sqrt r\in\mathbb{N} r ∈ N
namespace Loyalty { static int isqu ( unsigned long long x ) { if ( x == 0 ) return 0 ; int sh = __builtin_ctzll ( x ); int drop = ( sh & ~ 1 ); x >>= drop ; if ( x & 6 ULL ) return - 1 ; const unsigned long long xr = x ; unsigned long long z = ( 3 ULL - x ) >> 1 ; unsigned long long y = x * z ; for ( int i = 0 ; i < 5 ; ++ i ) { unsigned long long w = ( 3 ULL - z * y ) >> 1 ; y *= w ; z *= w ; } if ( y & ( 1 ULL << 62 )) y = 0 ULL - y ; y &= ~ ( 1 ULL << 63 ); if ( y >= ( 1 ULL << 32 )) return - 1 ; if ( y * y != xr ) return - 1 ; return ( int )( y << ( drop / 2 )); } int n , r , k ; double x ; inline int solve ( int a , int b , int c , int n ) { if ( ! n ) return 0 ; int g = gcd ( gcd ( a , b ), c ); a /= g , b /= g , c /= g ; int t = ( a * x + b ) / c ; if ( a * x + b == c ) return n ; else if ( t ) return n * ( n + 1 ) / 2 * t + solve ( a , b - c * t , c , n ); else { int nt = ( a * x + b ) * n / c ; return n * nt - solve ( a * c , - b * c , a * a * r - b * b , nt ); } } inline void init () {} inline void main ([[ maybe_unused ]] int _ca , [[ maybe_unused ]] int _atc ) { cin >> n >> r ; x = sqrt ( r ); if ( ~ ( k = isqu ( r ))) { if ( k & 1 ) cout << (( n & 1 ) ? - 1 : 0 ) << ' \n ' ; else cout << n << ' \n ' ; } else cout << n - 2 * solve ( 1 , 0 , 1 , n ) + 4 * solve ( 1 , 0 , 2 , n ) << ' \n ' ; } } 
喜欢的话，留下你的评论吧～