luogu P2424 约数和

嘟嘟嘟

求出[L, R]中每一个数的约数再相加必定会超时,所以换一种思路：枚举约数d。

对于一个约数d，能整除他的数可以写成k * d, (1 <= k <= ⌊n / d⌋)，因此约数d对答案的贡献是⌊n / d⌋ * d，f(i)表示[1, i]的约数和，那么f(n) = ∑⌊n / i⌋ * i  (1 <= i <= n)。因此x到y的答案等于f(y) - f(x - 1).

然而这样还是会TLE，考虑优化：对于⌊n / i⌋，以12为例打出一个表：12,6,4,3,2,2,1,1,1,1,1,1。想办法把相同的数字一次都算出来，令[L, R]表示相同的数的区间，那么L自然是上一次的R + 1,而R = n / (n / L)。因为⌊n / i⌋表示约数 i 在n中的出现次数，n / L就是约数，那么R = n / (n / L)。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<stack>

 #include<queue>

 #include<vector>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxp = 1e6 + ;

 inline ll read()

 {

   ll ans = ;

   char ch = getchar(), las = ' ';

   while(!isdigit(ch)) las = ch, ch = getchar();

   while(isdigit(ch)) ans = ans *  + ch - '', ch = getchar();

   if(las == '-') ans = -ans;

   return ans;

 }

 inline void write(ll x)

 {

   if(x < ) putchar('-'), x = -x;

   if(x >= ) write(x / );

   putchar(x %  + '');

 }

 int L, R, ans = ;

 ll sum(int n)

 {

   if(n <= ) return n;

   ll ans = ;

   for(ll L = , R; L <= n; L = R + )

     {

       R = n / (n / L);

       ans += (n / L) * (L + R) * (R - L + ) >> ;

     }

   return ans;

 }

 int main()

 {

   L = read(); R = read();

   write(sum(R) - sum(L - )); enter;

   return ;

 }