给定一个值N(1≤N≤10^7),在1~N得范围内,M次询问xi(xi≤N)的约数和。c++
时间: 2024-03-03 16:51:06 浏览: 20
以下是给定一个值N,在1~N得范围内,M次询问xi的约数和的 C++ 代码:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1e7 + 5;
int n, m;
int f[MAXN]; // f[i] 表示 i 的所有因数之和
void init()
{
memset(f, 0, sizeof(f)); // 初始化为 0
for (int i = 1; i <= n; i++) // 遍历每个数 i
{
for (int j = i; j <= n; j += i) // 遍历 i 的所有倍数 j
{
f[j] += i; // 累加因数 i
}
}
}
int main()
{
cin >> n >> m;
init(); // 预处理每个数的因数之和
for (int i = 0; i < m; i++) // 执行 m 次询问
{
int x;
cin >> x;
cout << f[x] << endl; // 输出 x 的因数之和
}
return 0;
}
```
这段代码首先输入正整数 N 和询问次数 M,然后通过 `init()` 函数预处理每个数的因数之和。对于每个询问,输入一个正整数 x,输出 x 的因数之和。预处理因数之和的过程中,遍历每个数 i,在 i 的所有倍数 j 上累加因数 i,最终得到每个数的因数之和。这样,对于每个询问,只需要在数组 f 中查找 x 的因数之和即可。