整除分塊

引入問題: ∑ i = 1 n ? n i ? \sum_{i=1}^n\lfloor \frac{n}{i}\rfloor ∑i=1n??in??,其中 n < = 1 0 9 n<=10^9 n<=109

暴力:

for(int i=1;i<=n;i++)
	ans+=n/i;//有手就行

這個的時間復雜度是 n 2 n^2 n2

正解:

i / j i/j i/j最終的答案一定是單調遞減的而且可能還有一段是連續的一段數字.

• 比如 20 20 20除下來的結果就是 20 , 10 , 6 , 5 , 4 , 3 , 2 , 2 , 2 , 2 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 20,10,6,5,4,3,2,2,2,2,1,1,1,1,1,1,1,1,1,1 20,10,6,5,4,3,2,2,2,2,1,1,1,1,1,1,1,1,1,1
• 所以我們每一次算出一段區間 l , r l,r l,r,個數就是 r ? l + 1 r-l+1 r?l+1然后答案就是 ( r ? l + 1 ) ? . . (r-l+1)*.. (r?l+1)?..就行了.
• 怎么求 l , r l,r l,r呢, r r r就是 i / ( i / j ) i/(i/j) i/(i/j),如果是 n n n的話就是 n / ( n / l ) n/(n/l) n/(n/l),挺好背的,干脆就先背住好了(有解釋,在后面)

for(int i=1,r;i<=n;i=r+1){
    r=n/(n/i);
    ans+=(r-i+1)*(n/i);
}

這個的時間復雜度是 n \sqrt{n} n ?

因為程序較多,所以手寫好了

字很丑,格式也沒有手打好看,不過只要能看就行啦,反正是學知識(強詞奪理)

例題1:求 ∑ i = 1 n ? n a i + b ? \sum_{i=1}^{n}\lfloor \frac{n}{ai+b} \rfloor ∑i=1n??ai+bn?? 其中 n , a , b n,a,b n,a,b已知

可以發現我們只是把 i i i變成了 a i + b ai+b ai+b,所以我們按照上面的推導方式再推導一次就行.

答案也容易求,就是和上面的一個步驟,求 r r r,用區間個數乘上 k k k就完事兒了.

例題2:求 ∑ i = 1 n ? n i 2 ? \sum_{i=1}^{n}\lfloor \frac{n}{i^2} \rfloor ∑i=1n??i2n??

和上道題差不多,可以用來鞏固一下,或者找找解題的感覺.

例題3:求 ∑ n = 1 M a x ∑ i = 1 n n % i \sum_{n=1}^{Max} \sum_{i=1}^{n}n\%i ∑n=1Max?∑i=1n?n%i 其中 1 ≤ n ≤ 1 0 5 1\le n \le 10^{5} 1≤n≤105

先把模運算換做除運算 n % i = n ? ? n i ? ? i n\%i=n-\lfloor \frac{n}i{} \rfloor * i n%i=n??in???i,然后就能出現我們熟悉的式子了,熟悉,但不完全熟悉,假設一個區間 l , r l,r l,r,在這個區間 ? n i ? \lfloor \frac{n}i{} \rfloor ?in??的值都一樣, i i i變大 1 1 1,那么整個式子就變小了 ? n i ? \lfloor \frac{n}i{} \rfloor ?in??,這個值是一個常數,所以就是一個等引數列,就可以 O 1 O1 O1的計算出來.

答案會溢位,所以對 998244353 998244353 998244353一個模吧.

#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
#define mod 998244353
using namespace std;
int Max,ans;
signed main(){
	scanf("%lld",&Max);
	for(int n=1;n<=Max;n++){
		for(int i=2,r,l;i<=n;){
			l=i; r=n/(n/i);
			ans=(ans+(r-l+1)*(n-n/i*i)-(n/i)*(r-l+1)*(r-l)/2)%mod;
			i=r+1;
		}
	}
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}

例題4:mmt

題目大意:求 c i = ∑ j = 1 i a ? i j ? b i % j c_i=\sum_{j=1}^{i}a_{\lfloor \frac{i}{j} \rfloor}b_{i\%j} ci?=∑j=1i?a?ji???bi%j?

上面那個題就是這個題的簡化版,上個題有的這個題就不解釋了.

• 這個題多了一個 a i a_i ai?,那我們再簡化一下求 c i = ∑ j = 1 i ? i j ? ? b i % j c_i=\sum_{j=1}^{i}{\lfloor \frac{i}{j} \rfloor}*b_{i\%j} ci?=∑j=1i??ji???bi%j?其實都是一樣的,我們把 i % j i\%j i%j變成 i ? ? i j ? ? j i-\lfloor \frac{i}{j} \rfloor * j i??ji???j, 也就是 c i = ∑ j = 1 i ? i j ? ? b i ? ? i j ? ? j c_i=\sum_{j=1}^{i}{\lfloor \frac{i}{j} \rfloor}*b_{i-\lfloor \frac{i}{j} \rfloor * j} ci?=∑j=1i??ji???bi??ji???j?,因為我們是每一個 ? i j ? \lfloor \frac{i}{j} \rfloor ?ji??都是一個區間一個區間的列舉,也就是上一個題的運算式前面再乘上 ? i j ? \lfloor \frac{i}{j} \rfloor ?ji??就行了,所以變成 a ? i j ? a_{\lfloor \frac{i}{j} \rfloor} a?ji???也一樣,乘上 a ? i j ? a_{\lfloor \frac{i}{j} \rfloor} a?ji???就行了.
• 然后也不是 i % j i\%j i%j了,套了一個 b b b在上面,假設原來是 9 + 7 + 5 + 3 + 1 9+7+5+3+1 9+7+5+3+1,現在就是求 b 9 + b 7 + b 5 + b 3 + b 1 b_9+b_7+b_5+b_3+b_1 b9?+b7?+b5?+b3?+b1?,既然是連續的,那我們為什么不用前綴和呢?相減不就得到了答案了嗎
• 所以我們預處理一個 s [ i ] [ j ] s[i][j] s[i][j]表示以 i i i結束,下標公差為 j j j的前綴和, j j j需要多少合適呢,總不可能開一個 1 0 5 ? 1 0 5 10^5*10^5 105?105的陣列吧,所以 j j j只需要 n \sqrt{n} n ?就行了公差超過這個的直接暴力列舉因為公差這么大,所以很快就弄完了.因為方便,我們直接把 j j j設為 200 200 200就行.
• 流程大概就是列舉一個 l , r l,r l,r然后求 l , r l,r l,r中的 b . . . b_{...} b...?之和乘上 a ? i j ? a_{\lfloor \frac{i}{j} \rfloor} a?ji???就行了.

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 100010
#define mod 123456789
#define int long long
using namespace std;
int n,a[maxn],b[maxn],s[maxn][205];
int calc(int n,int x,int l,int r){
	int ans=0;
	if(n<=200){
		if(l-n/x<0) ans=s[r][n/x];
		else ans=s[r][n/x]-s[l-n/x][n/x];
	}else{
		for(int i=x,temp=n/(n/x);i<=temp;i++) ans=(ans+b[n-i*(n/x)])%mod;
	}
	return (ans+mod)%mod;
}
int solve(int i){
	int ans=0;
	for(int j=1,r;j<=i;){
		r=i/(i/j);
		ans=(ans+a[i/j]*calc(i,j,i-r*(i/j),i-j*(i/j)))%mod;
		j=r+1;
	}
	return ans;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=0;i<n;i++)  scanf("%lld",&b[i]);
	for(int i=0;i<n;i++){
		for(int j=0;j<=200;j++){
			if(i>=j) s[i][j]=(s[i-j][j]+b[i])%mod;
			else s[i][j]=b[i];
		}
	}
	for(int i=1;i<=n;i++) printf("%lld\n",solve(i));
	return 0;
}

后記:這應該是我人生中第一個與整除分塊接觸的題,兩年前我抱著題解看了一下午也沒看懂……這個題noi.ac上好像已經不能評測了,但是這個題我覺得特別棒,如果能過樣例,應該能過(我是指大樣例),不行的話寫對拍也行.

例題5:Bamboo Partition

題意:給定 n n n個數 a 1 → a n a_1\to a_n a1?→an?,求一個最大的 d d d,滿足 ∑ i = 1 n d ? ( ( a [ i ] ? 1 ) % d + 1 ) ≤ k \sum_{i=1}^{n}d-((a[i]-1)\%d+1)\le k ∑i=1n?d?((a[i]?1)%d+1)≤k.

• 最開始想的是二分,結果不是,因為這個 d d d和最終的和(記為 a n s ans ans)根本不是線性的.

• 所以我們現在開始化簡這個式子,但是我們要先知道 % \% %運算怎么變成除運算 x % y = x ? y ? ? x y ? x\%y=x-y*\lfloor \frac{x}{y} \rfloor x%y=x?y??yx??其實這個也挺好理解的, ? x y ? \lfloor \frac{x}{y} \rfloor ?yx??就是去掉余數,在乘上就行了,這個應該挺好理解的.所以原式就變成了
  ∑ i = 1 n d ? ( a i ? d ? ? a i ? 1 d ? ) ≤ k d ? ( n + ∑ i = 1 n ? a i ? 1 d ? ) ≤ k + ∑ i = 1 n a i \sum_{i=1}^{n}d-(a_i-d*\lfloor \frac{a_i-1}{d} \rfloor)\le k\\ d*(n+\sum_{i=1}^{n}\lfloor \frac{a_i-1}{d} \rfloor)\le k+\sum_{i=1}^{n}a_i i=1∑n?d?(ai??d??dai??1??)≤kd?(n+i=1∑n??dai??1??)≤k+i=1∑n?ai?

• 到這個地方貌似和整除分塊沒啥關系….

• 第一種方法:現在我們需要列舉 d d d,然后 ∑ i = 1 n ? a i ? 1 d ? \sum_{i=1}^{n}\lfloor \frac{a_i-1}{d} \rfloor ∑i=1n??dai??1??其實是只有 m a x { a i } \sqrt {max\ \{a_i\}} max {ai?} ?種方法的,參考整除分塊,除下來的結果最多只有 n \sqrt n n ?個答案的,也就是說我們只需要列舉 1 → n 1\to \sqrt n 1→n ?就行(這個是其中一種方法,我暫時還沒做)

• 第二種方法:直接把右邊 k + ∑ i = 1 n a i k+\sum_{i=1}^{n}a_i k+∑i=1n?ai?加起來(記作 s u m sum sum),再來看左邊,當 d ≤ s u m d\le\sqrt {sum} d≤sum ?時 ( n + ∑ i = 1 n ? a i ? 1 d ? ) (n+\sum_{i=1}^{n}\lfloor \frac{a_i-1}{d} \rfloor) (n+∑i=1n??dai??1??)是必須大于等于 s u m \sqrt{sum} sum ?的,同理 d ≥ s u m d\ge \sqrt{sum} d≥sum ?時, ( n + ∑ i = 1 n ? a i ? 1 d ? ) (n+\sum_{i=1}^{n}\lfloor \frac{a_i-1}{d} \rfloor) (n+∑i=1n??dai??1??)是必須小于等于 s u m \sqrt{sum} sum ?的(不然式子不成立).所以列舉 s u m \sqrt{sum} sum ?次就行

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 200
#define int long long
using namespace std;
int n,a[maxn],k,ans,Max;
int calc(int d){
	int Ans=0;
	for(int i=1;i<=n;i++) Ans+=(a[i]-1)/d;
	return Ans;
}
bool check(int d) {return n*d+calc(d)*d<=k;}
signed main(){
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),k+=a[i],Max=max(Max,a[i]);
	for(int i=1;i*i<=Max;i++){
		if(check(i)) ans=max(ans,i);
		if(check(k/i)) ans=max(ans,k/i);
	}
	printf("%lld\n",ans);
	return 0;
}

行啦,講完了,算是入門了,以后有題在弄上來,聽說莫比烏斯反演里面用的多.