我试图找出给定范围a,b ac的所有因子之和。
我试着从a循环到b并求出c的所有除数之和,但这似乎是无效的,因为a和b之间的绝对差可以是10^9。
有没有减少这种方法的时间复杂度的方法?

int a, b, c;
cin >> a >> b >> c;
long long sum = 0;
for (int i = a; i <= b; i++) {
    if (i % c == 0) {
       ans += i;
    }
}
cout << sum << endl;

最佳答案

首先确定所有是c的除数的素数这会给你留下一个数字列表[w,x,y,z…]然后在这个列表中保留一个散列表集合,其中包含整数的所有倍数,这些倍数也是除数。

int a, b, c;
cin >> a >> b >> c;
long long sum = 0;

std::vector<int> all_prime_factors = // Get all prime factors of c
std::unordered_set<int> factorSet;
for (int primefactor : all_prime_factors)
{
    int factor = primefactor;
    while (factor <= b)
    {
        if (factor % c == 0)
            factorSet.insert(factor);
        factor += primefactor;
    }
}

for (int x : factorSet)
{
    sum += x;
}

cout << sum << endl;

07-24 09:47
查看更多