2022没封的网站免费的,网站建设基础大纲文案,如何制作小程序图片,qnap如何搭wordpress题目
给定 n 个正整数 ai#xff0c;请你输出这些数的乘积的约数之和#xff0c;答案对 1097 取模。
输入格式
第一行包含整数 n。
接下来 n 行#xff0c;每行包含一个整数 ai。
输出格式
输出一个整数#xff0c;表示所给正整数的乘积的约数之和#xff0c;答案需…题目
给定 n 个正整数 ai请你输出这些数的乘积的约数之和答案对 1097 取模。
输入格式
第一行包含整数 n。
接下来 n 行每行包含一个整数 ai。
输出格式
输出一个整数表示所给正整数的乘积的约数之和答案需对 1097 取模。
数据范围
1≤n≤100 1≤ai≤2×1e9
输入样例
3
2
6
8输出样例
252
思路
首先使用unordered_map primes 来记录每个质因子及其出现的次数。
然后对于每个输入的数x通过质因数分解的方法将x进行质因数分解并统计每个质因子的次数。如果x仍然大于1说明x本身就是一个质因子将其次数加1。
接下来遍历primes中的每个质因子及其次数。对于每个质因子a计算它的幂和(a^b 1) % mod其中b为该质因子的次数。最后将每个质因子的幂和乘到约数和中得到最终的约数和。
最后输出约数和的结果。
其中用到公式 其中p1~pk代表质因数c1~ck代表质因数个数 结束后t为
t a^b a^(b-1) a^(b - 2) .... a^3 a^2 a^1 a^0
代码
#include iostream
#include algorithm
#include unordered_map
#include vectorusing namespace std;typedef long long LL;const int N 110, mod 1e9 7;int main()
{int n;cin n; // 输入n表示有n个数unordered_mapint, int primes; // 使用unordered_map来记录质因子及其次数while (n -- ){int x;cin x; // 输入每个数xfor (int i 2; i x / i; i )while (x % i 0) // 对x进行质因数分解并统计每个质因子的次数{x / i;primes[i] ;}if (x 1) primes[x] ; // 如果x仍然大于1说明x本身就是一个质因子将其次数加1}LL res 1; // 初始化约数和为1for (auto p : primes) // 遍历primes中的每个质因子及其次数{LL a p.first, b p.second; // 质因子a和其次数bLL t 1; // 计算质因子a的幂和while (b -- ) t (t * a 1) % mod;res res * t % mod; // 将质因子a的幂和乘到约数和中}cout res endl; // 输出约数和return 0;
}题目来自871. 约数之和 - AcWing题库
