范围内可被k整除的所有整数的总和
有没有办法计算这个范围内的总和，它可以被 k 整除，时间复杂度为：O(1)
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long a = in.nextLong();
long b = in.nextLong();
long k = in.nextLong();
long SUM=0;
for (long i = a; i <= b; i++) {
if(i%k==0){
SUM+=i;
}
}
System.out.println(SUM);
}
回答
O(1) 基本上意味着您需要一个公式来计算该总和。
考虑范围内所有数字的公式，(start + end) * numValues / 2您可以执行以下操作：
//if a already is a multiple of k just use it, otherwise find the next larger one
int start = a % k == 0? a : a + k - a%k;
//find the divisible of k that is equal to b or the next smaller one
int end = b - b%k;
//the number of values is the number of times k fits into the range
int num = ((end - start) / k) + 1;
//apply the formula
int sum = (start + end) * num / 2;