文章目錄

• 前提知識復習
• T1：余數求和
• • title
  • solution
  • code
• T2：Ice Rain
• • title
  • solution
  • code
• T3：The Fool
• • title
  • solution
  • code
• T4：模積和
• • title
  • solution
  • code

前提知識復習

整除分塊是用于快速處理形似下列式子的方法，是解決莫比烏斯反演類題目需要掌握的前提知識
$$\sum _{i=1}^n?\frac{n}{i}?$$
但是本篇博客的例題是特別特別板的，不會涉及莫比烏斯反演，請dalao們出門左轉別浪費時間，蟹蟹
回歸正題，很顯然上面的式子可以$O(n)$得到答案
但是，在某些題目中，毒瘤出題人將數據加強到了 $10^{10}$以上
這個時候我們就無法通過$O(n)$ 的解法來得到答案
我們需要一個$O(\sqrt{n})$的更為優秀的解法

對于單一的$?\frac{n}{i}?$，某些地方的值是相同的，并且呈塊狀分布
通過深入的探求規律與嚴密推理以及暴力打表與幸運瞎猜 ，最后驚奇的發現這些塊狀分布的值是有規律的
對于一個塊，假設它的起始位置的下標為$l$，那么可以得到的是，它的結束位置的下標為
代碼表示即為

r = n / ( n / l );

分塊如果非要安排一個模板的話，那就是一個$for$循環了

int calc( int n ) {int ans = 0;for( int l = 1, r;l <= n;l = r + 1 ) {r = n / ( n / l );//根據題目要求進行計算 }return ans; }

有的時候不同的題目可能出現$n/l==0$的情況，為了防止程序掛掉，我們也可以這么寫

int calc( int n ) {int ans = 0;for( int l = 1, r;l <= n;l = r + 1 ) {if( k / l ) r = min( k / ( k / l ), n );else r = n;//根據題目要求進行計算}return ans; }

具體的就用例題來體會吧

T1：余數求和

title

添加鏈接描述

solution

$$G(n,k)=\sum _{i=1}^{n}kmodi=\sum _{i=1}^n(k??\frac{k}{i}??i)=\sum _{i=1}^{n}k?\sum _{i=1}^n?\frac{k}{i}??i$$
前面的求和式子可以很直觀地得到${\sum }_{i=1}^{n}k=n?k$
后面的求和式子我們令$l$表示這個塊的開始下標，$r$為這個塊的結束下標，$T=?\frac{n}{i}?$，則該塊里面的值為：
$$\sum _{i=l}^{r}T?i=\sum _{i=l}^{r}T?\sum _{i=l}^{r}i$$
答案顯而易見了吧，第一個求和就是個定值$(r?l+1)?T$，后面的求和就是等差數列

計算方法：首項加末項乘以項數除以二=>$(l+r)?(r?l+1)/2$

code

#include <cstdio> #include <iostream> using namespace std; #define int long long signed main() {int n, k;scanf( "%lld %lld", &n, &k );int ans = n * k;for( int l = 1, r;l <= n;l = r + 1 ) {if( k / l ) r = min ( k / ( k / l ), n );else r = n;ans -= ( r - l + 1 ) * ( k / l ) * ( l + r ) / 2;}printf( "%lld", ans );return 0; }

T2：Ice Rain

title

添加鏈接描述

solution

讀完題后是不是

一模一樣的吧，這種sb題 你加一個無線輸入操作就$AC$，$pass$，下一個！！

code

#include <cstdio> #include <iostream> using namespace std;int main() {long long n, k;while( ~ scanf( "%lld %lld", &n, &k ) ) {long long ans = n * k;for( long long l = 1, r;l <= n;l = r + 1 ) {if( k / l ) r = min( k / ( k / l ), n );else r = n;ans -= ( k / l ) * ( l + r ) * ( r - l + 1 ) / 2;}printf( "%lld\n", ans );}return 0; }

T3：The Fool

title

添加鏈接描述

solution

一樣的吧？差不多的吧？如果你沒有一點思路的話，證明我寫的太差 沒有學懂哦~
${\sum }_{i=1}^n?\frac{n}{i}?$，先分出每個塊，然后再等差數列求和，加在一起最后判斷，$van$事

code

#include <cstdio> int main() {int T;scanf( "%d", &T );for( int Case = 1;Case <= T;Case ++ ) {long long n;scanf( "%lld", &n );long long ans = 0;for( int l = 1, r;l <= n;l = r + 1 ) {r = n / ( n / l );ans += ( r - l + 1 ) * ( n / l );} if( ans & 1 ) printf( "Case %d: odd\n", Case );else printf( "Case %d: even\n", Case );}return 0; }

T4：模積和

title

添加鏈接描述

solution

這道題就是個重頭戲了，其實也很簡單的
仔細看推導過程！！
$$ans=\sum _{i=1}^n\sum _{j=1}^m(nmodi)\times (mmodj),i=j$$
用容斥拆開把$i=j$的情況減掉即可
$$ans=\sum _{i=1}^n\sum _{j=1}^m(nmodi)\times (mmodj)?\sum _{i=1}^{min(n,m)}(nmodi)\times (mmodi)$$
直接把顯而易見能分塊的先分了來，再暴力展開
$$\sum _{i=1}^n(nmodi)=\sum _{i=1}^{n}n?\sum _{i=1}^n?\frac{n}{i}??i$$
$$\sum _{j=1}^m(mmodj)=\sum _{j=1}^{m}m?\sum _{j=1}^m?\frac{m}{j}??j$$
$$\sum _{i=1}^{min(n,m)}(nmodi)\times (mmodi)=\sum _{i=1}^{min(n,m)}(n??\frac{n}{i}??i)?(m??\frac{m}{i}??i)$$
$$=\sum _{i=1}^{min(n,m)}(nm+?\frac{m}{i}??\frac{n}{i}?i^2??\frac{m}{i}?i??\frac{n}{i}?i)$$
整理綜上

$$ans=(\sum _{i=1}^{n}n?\sum _{i=1}^n?\frac{n}{i}??i)(\sum _{i=1}^{m}m?\sum _{i=1}^m?\frac{m}{i}??i)?\sum _{i=1}^{min(n,m)}(nm+?\frac{m}{i}??\frac{n}{i}?i^2??\frac{m}{i}?i??\frac{n}{i}?i)$$
最后我們發現$i^2$在分塊的時候掛掉了，OMG，怎么辦！！，告訴你一個結論

$$\sum _i^n{i}^2=n?(n+1)?(2n+1)/2$$

最后注意避雷！！！$p$不是個質數，稍微用隨便找個互質的數搞個逆元就好了

code

#include <cstdio> #include <iostream> using namespace std; #define int long long #define mod 19940417 int n, m, inv;int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }int sqr( int x ) {return x * ( x + 1 ) % mod * ( x << 1 | 1 ) % mod * inv % mod; }int sum( int l, int r ) {return ( l + r ) * ( r - l + 1 ) / 2 % mod; }int calc( int n ) {int ans = 0;for( int l = 1, r;l <= n;l = r + 1 ) {r = n / ( n / l );ans = ( ans + n * ( r - l + 1 ) % mod - ( n / l ) * sum( l, r ) % mod + mod ) % mod;}return ans; }signed main() {inv = qkpow( 6, 17091779 );scanf( "%lld %lld", &n, &m );int ans = calc( n ) * calc( m ) % mod;if( n > m ) swap( n, m );for( int l = 1, r;l <= n;l = r + 1 ) {r = min( n / ( n / l ), m / ( m / l ) );int sum1 = n * m % mod * ( r - l + 1 ) % mod;int sum2 = ( n / l ) * ( m / l ) % mod * ( sqr( r ) - sqr( l - 1 ) + mod ) % mod;int sum3 = ( n / l * m % mod + m / l * n % mod ) * sum( l, r ) % mod;ans = ( ans - ( sum1 + sum2 - sum3 + mod ) % mod + mod ) % mod;}printf( "%lld", ans );return 0; }

走了，題還沒做完…

總結

以上是生活随笔為你收集整理的数论分块专题复习（余数求和+模积和+Ice Rain+The Fool）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。