当前位置：首页 > web >正文

算法笔记·数学·约数之和

web 2025/8/1 17:18:32

题目：（来源：AcWing）

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 1e9+7 取模。

输入格式

第一行包含整数 n。

接下来 n行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7 取模。

数据范围

1≤n≤100,
1≤ai≤2×1e9

输入样例：

输出样例：

思路：

1.一个数可以拆解为多个质数的n次方的积，即 $n=p_1^{x_1}*p_2^{x_2} *...p_i^{x_i}$ ，例如 $8=2^3$ 。

2.n的约数即为 $p_1{p_2}...{p_n}$ 的x次方组合（ $x\epsilon[0,x_i]$ ）。

3.于是有，约数之和等于 $(1+p_1+p_1^2+...+p_1^{x_1})*(1+p_2+p_2^2+...+p_2^{x_2})*...*(1+p_i+p_i^2+...+p_i^{x_i})$

4.求 $(1+p_i+p_i^2+...+p_i^{x_i})$ 可以用迭代法， $sum_{x_{i}}=sum_{x_{i-1}}*p_i+1$ %mod，这样可以避免超出int范围。

代码:

#include<iostream>
#include<unordered_map>
using namespace std;
const int mod = 1e9+7;int n;
unordered_map<int ,int> m;void check(int x)
{int t = x;for(int i = 2;i <= t/i ;i++){while(t%i == 0){t/=i;m[i]++;}}if(t > 1) m[t]++;}// int fun1(int a,int b)
// {
//     if(b==0) return 1;
//     return a*fun1(a,b-1)%mod;
// }int main()
{cin>>n;while(n--){int x;scanf("%d",&x);check(x);}long long res = 1;for(auto it = m.begin();it!=m.end();it++){int a = it->first,b=it->second;long long t = 1;while(b--) t = (t*a+1)%mod;res= res * t % mod;}cout <<res;return 0;
}

查看全文

http://www.xdnf.cn/news/8754.html