题解 P2424 【约数和】

# 除法分块模板题 首先，先不说除法分块，我们先想思路 ### 1.暴力枚举 ```cpp #include <bits/stdc++.h> using namespace std; int a,b; int f(int x) { int s=0; for(int i=1;i*i<=x;i++) { if(x%i==0) s+=i+x/i; if(i*i==x) s-=i; } // printf("%d %d\n",x,s); return s; } int main() { int sum=0; cin>>a>>b; for(int i=a;i<=b;i++) { sum+=f(i); } cout<<sum; return 0; } ``` 直接枚举所有数，再求约数之和 复杂度O(n^3/2) 20分 ### 2.设f[x]为1~x的约数和，我们发现所求的，就是f[b]-f]a] 对于求1~x的约数之和，有一个方法： 你仔细观察，会发现一个事情：（一下除都是整除） **1这个因子被选了n/1次，2被选了n/2次，以此类推，x被选了n/x次** 举个例子：4 1=1 2=1+2 3=1+3 4=1+2+4 1被选了4次，2被选了2次，3被选了1次，4被选了1次 所以简单来说， ### f[x]=∑n/i *(i) (1<=i<=x) 直接o(n)扫一遍，60分 ------------ 那到底怎么做呢？ ## 正解：除法分块 什么叫除法分块？又该怎么写？ 拿100来说，我们发现 100/51=1 100/52=1 …… 100/99=1 100/100=1 我们发现51~100那么大一段数，他们的n/i都是1，所以我们可以对其合并，将51~100这一段的值合并为1*（51+……+100），然后用等差数列求和公式O（1）求出即可 所以，简单来说 **除法分块就是把一些n/i值相等的部分合并，用等差数列公式求出** 怎么写？ 还是以100为例 首先，设r=100 在r不为0的情况下循环 m=100/r=1 l=x/(m+1)+1=51 在l~r中n/i恒为m=1 所以，s+=m*(r+l)*(r-l+1)/2 然后下一个 ， r = l-1 =50 代码： ``` i8 slove(i8 x) { i8 s=0; // for(int i=1;i<=x;i++) s+=x/i*i; i8 r=x; while(r) { i8 m=x/r; i8 l=x/(m+1)+1; s+=(r+l)*(r-l+1)*m/2; r=l-1; } return s; } ``` ------------ 完整代码： ```cpp #include <bits/stdc++.h> #define i8 __int128 #define ll long long using namespace std; const int R = 2e9; void print(i8 n) { if(n>9) print(n/10); putchar(n%10+48); } i8 ans; i8 slove(i8 x) { i8 s=0; // for(int i=1;i<=x;i++) s+=x/i*i; i8 r=x; while(r) { i8 m=x/r; i8 l=x/(m+1)+1; s+=(r+l)*(r-l+1)*m/2; r=l-1; } return s; } int x,y; int main() { cin>>x>>y; print(slove(y)-slove(x-1)); return 0; } ```