https://www.luogu.org/problemnew/show/P2424
记 \(\sigma(n)\) 为n的所有约数之和,例如 \(\sigma(6)=1+2+3+6=12\) .
求 \(ans(n)=\sum\limits_{i=x}^{y}\sigma(i)\) .
首先,记 \(f(n)=\sum\limits_{i=1}^{n}\sigma(i)\) ,则 \(ans(n)=f(y)-f(x-1)\) .
对于 \(f(n)=\sum\limits_{i=1}^{n}\sigma(i)\) ,一个直接的做法是枚举i然后枚举i的因子求和,显然会TLE.
考虑直接枚举因子,易知 \(n\) 以内 \(d\) 的一共有 \(\lfloor\frac{n}{d}\rfloor\) 个,
则有 $f(n)=\sum\limits_{d=1}^{n} d * \lfloor\frac{n}{d}\rfloor $ ,类似的形式在余数求和中见过,直接复制:
记 $ c= \lfloor\frac{n}{d}\rfloor $ 则每段 \(d\) 对应相同的一个 \(c\)
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static void solve(Scanner cin,PrintStream cout){
while(cin.hasNext()){
long x=cin.nextLong(),y=cin.nextLong();
cout.println(sumfenkuai(y)-sumfenkuai(x-1));
}
}
public static long sumfenkuai(long n){
long ans=0;
for(long l=1,r; l<=n; l=r+1) {
if(n/l!=0) {
r=Math.min(n/(n/l),n);
} else {
//n/l==0，意味着l>n，所有的后面的下整都是0，分成同一块
r=n;
break;
}
//d={l,l+1,...r}
//sum(d)=(l+r)*(r-l+1)/2
//c=n/l=n/r
//ans=sum_d=1^n:(sum(d)*c)
ans+=(n/l)*(r-l+1)*(l+r)/2;
}
return ans;
}
public static void main(String[] args) {
//setFileIO("D://test");
Scanner cin=new Scanner(System.in);
PrintStream cout=new PrintStream(System.out);
solve(cin,cout);
cin.close();
cout.close();
}
public static void FileIO(String filename){
FileInputStream fis = null;
try {
fis = new FileInputStream(filename+".in");
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.setIn(fis);
PrintStream ps = null;
try {
ps = new PrintStream(new FileOutputStream(filename+".out"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.setOut(ps);
}
}