整除分块练习题

P1403 [AHOI2005] 约数研究

 思路：f[i]表示的是，对于i的因子的个数

我们还是可以用整除分块，但是我们遍历的是因子了，我们的最小因子一定是1，最大因子是n，对于当前i这个因子，有n/i个数含有当前因子，直接用整除分块板子，去求出来范围，然后乘上这个范围有当前因子的个数累加和即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
signed main()
{cin >> n;int ans = 0;for (int l = 1, r; l <= n;l=r+1){r = (n / (n / l));ans += (r - l + 1) * (n / l);}cout << ans;return 0;
}

P2424 约数和

这题和上面那一题很像，只是将f(x)的定义改为了x的因子的和

思路：我们可以很轻松的想到，其实可以视作f(1~y)-f(1~x-1),我们还是和上面那一题一样去遍历整个因子的范围，也就是从1~n,我们可以想到，其实就是∑ i * n/i,但是这样去遍历i的时间复杂度为O（n）是不能被接受的，我们应当去考虑整除分块，我们有一块区域的个数都是(n/i)个，那么我们找到左右区间，这个区间的累加和就是(r-l+1)*(l+r)/2，然后再去乘上个数即可

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int x, y;
int solve(int n)
{int ans = 0;for (int l = 1,r; l <= n;l=r+1){r = n / (n / l);ans += n / l * (r - l + 1) * (l + r) / 2;}return ans;
}
signed main()
{cin >> x >> y;cout << solve(y) - solve(x - 1);return 0;
}

 P2261 [CQOI2007] 余数求和

思路：我们可以将k mod i 转换一下，可以变成k-i*(k/i),这样的话就变成了n*k-∑ i * (k/i)，然后就可以对后半部分进行整除分块了，和上面那个分块的公式一样的

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
int ans;
signed main()
{cin >> n >> k;ans = n * k;for (int l = 1, r; l <= n;l=r+1){r = n / (n / l);ans -= k / l * (r - l + 1) * (l + r) / 2;}cout << ans;return 0;
}

C. Floor and Mod

思路：这题是真的难啊，我们一步一步分析

首先知道a/b=a%b

那么就有0<=a%b<b  ->  0<=a/b<b -> 0<=a/(b+1)<b

然后将b+1挪到两边，得到 0 <= a < b*b+b

可以得到 0<= a <= b*b+b-1

然后对题目分析可知 a=b*x+x 得到 a/(b+1) = x

那么在取值范围内，a可能存在的个数为(b*b+b-1)/(b+1)个

然后我们要判断b*b+b-1和x的大小，如果b*b+b-1小的话，那就直接枚举，如果是x小的话，那就是整除分块板子，时间复杂度为根号n

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long longvoid solve()
{int x, y;cin >> x >> y;int ans = 0;int max_b = min(y, (int)sqrt(x) + 1);for (int b = 1; b <= max_b; ++b){int q_max = x / (b + 1);int q_lim = min(b - 1, q_max);if (q_lim >= 1){ans += q_lim;}}for (int l = max_b + 1, r; l <= y; l = r + 1){int q = x / (l + 1);if (q == 0)break;r = min(y, x / q - 1);ans += (r - l + 1) * q;}cout << ans << "\n";
}signed main()
{int t;cin >> t;while (t--){solve();}return 0;
}