java - 可被 k 整除的范围内所有整数的总和

Question

有没有办法计算这个范围内能被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);
}

Answer 1

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;