我试图找出给定范围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;