称一个正整数对 ( a , b ) (a, b) ( a , b ) k k k k k k ( h 1 , w 1 ) , ( h 2 , w 2 ) , ⋯ , ( h k , w k ) (h_1, w_1), (h_2, w_2), \cdots, (h_k, w_k) ( h 1 , w 1 ) , ( h 2 , w 2 ) , ⋯ , ( h k , w k )
∑ i = 1 k h i w i = a \sum_{i = 1} ^ k h_iw_i = a ∑ i = 1 k h i w i = a ∑ i = 1 k 2 ( h i + w i ) = b \sum_{i = 1} ^ k 2(h_i + w_i) = b ∑ i = 1 k 2 ( h i + w i ) = b 给定 s , c s, c s , c a ∈ [ 1 , s ] , b ∈ [ 1 , c ] a \in [1, s], b \in [1, c] a ∈ [ 1 , s ] , b ∈ [ 1 , c ]
对于 100 % 100\% 1 0 0 % 1 ≤ s ≤ 2 × 1 0 5 , 1 ≤ c ≤ 4 × 1 0 5 , 2 ∣ c 1 \le s \le 2 \times 10^5, 1 \le c \le 4 \times 10^5, 2 \mid c 1 ≤ s ≤ 2 × 1 0 5 , 1 ≤ c ≤ 4 × 1 0 5 , 2 ∣ c
这里先把 c c c 2 2 2
不妨设 h i ≤ w i h_i\leq w_i h i ≤ w i h i ≤ s h_i\leq \sqrt s h i ≤ s
如果存在 h i = h j h_i=h_j h i = h j ( h i , w i ) , ( h i , w j ) (h_i,w_i),(h_i,w_j) ( h i , w i ) , ( h i , w j ) ( h i , w i + w j − 1 ) , ( 1 , h i ) (h_i,w_i+w_j-1),(1,h_i) ( h i , w i + w j − 1 ) , ( 1 , h i )
然后 1 1 1 ( 1 , x ) , ( 1 , y ) (1,x),(1,y) ( 1 , x ) , ( 1 , y ) ( 1 , x + y − 1 ) , ( 1 , 1 ) (1,x+y-1),(1,1) ( 1 , x + y − 1 ) , ( 1 , 1 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) h h h w w w
如果把 ( 1 , 1 ) (1,1) ( 1 , 1 ) 2 a − b 2a-b 2 a − b f i f_i f i 2 a − b = i 2a-b=i 2 a − b = i b b b
然后枚举 h , w h,w h , w f i ← f i − ( 2 h w − h − w ) + h + w f_i\leftarrow f_{i-(2hw-h-w)}+h+w f i ← f i − ( 2 h w − h − w ) + h + w
把底下那玩意拆开，f i ← f i + h − w ( 2 h − 1 ) + h + w f_i\leftarrow f_{i+h-w(2h-1)}+h+w f i ← f i + h − w ( 2 h − 1 ) + h + w
这样就只要枚举 h h h g i g_i g i j + h − w ( 2 h − 1 ) = i j+h-w(2h-1)=i j + h − w ( 2 h − 1 ) = i f j + w f_j+w f j + w g i = min { f i , g i − ( 2 h − 1 ) + 1 } g_i=\min\{f_i,g_{i-(2h-1)}+1\} g i = min { f i , g i − ( 2 h − 1 ) + 1 }
所以 f i = g i + h + h f_i=g_{i+h}+h f i = g i + h + h
然后统计答案就枚举那个 2 a − b 2a-b 2 a − b i i i b b b 2 ∣ ( i + b ) 2|(i+b) 2 ∣ ( i + b ) f i ≤ b ≤ 2 n − i f_i\leq b\leq 2n-i f i ≤ b ≤ 2 n − i
时间复杂度：O ( s s ) O(s\sqrt s) O ( s s )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <bits/stdc++.h> const int kMaxN = 5e5 + 5 ;int n, m;int f[kMaxN], g[kMaxN];void dickdreamer () 2 ;memset (f, 0x3f , sizeof (f));for (int i = 1 ; i <= n; ++i)1 ] = i + 1 ;for (int h = 2 ; h * h <= n; ++h) {swap (f, g);for (int i = 0 ; i <= 2 * n; ++i)0 ] = 0 ;for (int i = 0 ; i <= 2 * n + h; ++i) {if (i > 2 * n) g[i] = 1e9 ;if (i >= 2 * h - 1 ) g[i] = std::min (g[i], g[i - (2 * h - 1 )] + 1 );for (int i = 0 ; i <= 2 * n; ++i)min (f[i], g[i + h] + h);int64_t ans = 0 ;for (int i = 0 ; i <= 2 * n; ++i) {int l = f[i] + ((i + f[i]) & 1 ), r = std::min (m, 2 * n - i);if (l <= r) ans += (r - l) / 2 + 1 ;'\n' ;int32_t main () #ifdef ORZXKR freopen ("in.txt" , "r" , stdin);freopen ("out.txt" , "w" , stdout);#endif sync_with_stdio (0 ), std::cin.tie (0 ), std::cout.tie (0 );int T = 1 ;while (T--) dickdreamer ();return 0 ;