數論分塊一般解決的就是形如（這種式子的求解）

**

例一：bzoj1968: [Ahoi2005]COMMON 約數研究

**

Description

Input
只有一行一個整數 N（0 < N < 1000000）。

Output
只有一行輸出，為整數M，即f(1)到f(N)的累加和。

題目分析
答案即為1…x1…x的所有約數個數和。

#include<bits/stdc++.h> typedef long long ll;int n; ll ans;int main() {register int i,j;scanf("%d",&n);for (i=1; i<=n; i=j+1){j = n/(n/i);//j代表當前下一個位置 下一個位置是指n/i不同于上一個的位置 ans += 1ll*(j-i+1)*(n/i);//j-i+1是總數 }printf("%lld\n",ans);return 0; }

[CQOI2007]余數求和

#include<cstdio> #include<iostream> #include<algorithm> #define ll long long using namespace std; int main() { ll n,k;cin>>n>>k;ll ans;ans=n*k;for(ll i=1,r;i<=n;i=r+1){ if(k/i!=0)r=min(k/(k/i),n);//注意這個min如果 n 太小的話 會出現bugelse// mod 大于n時 r=n;ans-=(k/i)*(r-i+1)*(i+r)/2;//(i+r)/2是用一個等差數列求和 公式= （a1+an）/2} cout<<ans<<endl; }

BZOJ2956 (模積和)

Description
　求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。

Input
第一行兩個數n,m。

Output
　　一個整數表示答案mod 19940417的值

Sample Input
3 4

Sample Output
1
樣例說明
答案為(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1數據規模和約定
對于100%的數據n,m<=10^9。

總結

以上是生活随笔為你收集整理的数论分块入门的全部內容，希望文章能夠幫你解決所遇到的問題。

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