首页 > 其他分享 >AcWing 870. 约数个数

AcWing 870. 约数个数

时间:2024-07-24 11:22:06浏览次数:19  
标签:约数 int 个数 870 ai 1e9 质因数 AcWing

题目叙述:

题目链接:https://www.acwing.com/video/295/

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

输入格式

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

输出格式

输出一个整数,表示所给正整数的乘积的约数个数,答案需对 1e9 + 7取模。

数据范围

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

输入样例:

3
2
6
8

输出样例:

12

直接上代码并解释:

#include<iostream>
#include<unordered_map>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
	int n; cin >> n;
	//定义map容器存储所有的x的质因数的个数之和
	unordered_map<int, int> prime;
	while (n--) {
		int x; cin >> x;
		//找出x的所有质因数的个数
		for (int i = 2; i <= x / i; i++) {
			if (x % i == 0) {
				while (x % i == 0) {
					x /= i;
					prime[i]++;
				}
			}
		}
		if (x > 1) prime[x]++;
	}
	long long res = 1;
	//将每个数的所有质因数之和相乘,结果就是答案
	for (auto num : prime) res = res * (num.second + 1) % mod;
	cout << res;
	return 0;
}

标签:约数,int,个数,870,ai,1e9,质因数,AcWing
From: https://www.cnblogs.com/Tomorrowland/p/18320439

相关文章

  • 洛谷P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    [NOIP2001普及组]最大公约数和最小公倍数问题题目描述洛谷题目链接:https://www.luogu.com.cn/problem/P1029输入两个正整数x,y,求出满足下列条件的P,Q的个数:P,Q是正整数。要求P,Q以x为最大公约数,以y为最小公倍数。试求:满足条件的所有可能的P,Q的个数。......
  • 约数和倍数的性质
    约数(Divisors)约数是指能整除某个整数的其他整数。例如,对于整数(a),如果存在整数(b)使得(a=b*c),那么(b)就是(a)的约数。性质:1和自身是每个整数的约数:每个整数(a)都有至少两个约数:1和(a)本身。约数的范围:如果(d)是(n)的一个约数,则(d......
  • acwing学习笔记-数学知识
    文章目录数学知识一、质数1、试除法判定质数2、开方判定质数3、分解质因数4、筛质数(1)、埃氏筛法(2)、线性筛二、约数1、试除法求约数2、约数个数总结数学知识数学真是一个令人摸不着头脑的一个东西,小小的质数都可以把你拿捏得死死的一、质数1、试除法判定质......
  • 最小公约数与最大公倍数(1)
    最小公约数\((a,b)\)即满足\(d\mida,d\midb\)的最大\(d\)最大公倍数\([a,b]\)即满足\(a\midd,b\midd\)的最小\(d\)若\((a,b)=1\)称\(a,b\)两数互素重要结论:\((a,b)[a,b]=ab\)裴蜀定理:\(ax+by=c\)有整数解\((x,y)\)当且仅当\((a,b)\midc\)证明......
  • 最小公约数与最大公倍数(2)
    CP3一些大小估计类问题经典的估计是\((a,b)\lea-b,[a,b]\ge\frac{ab}{a-b}\),从而\(\sum_{k=0}^{n-1}\frac1{[a_k,a_{k+1}]}\le1-\frac1{2^n}\)(归纳,分类\(a_n<2^n,a_n\ge2^n\)即可)此外,\(gcd\)可以用欧拉函数表达,参见欧拉函数例1求证:\([m,n]+[m+1,n+1]\ge\fra......
  • AcWing 2074:倒计数 ← 双指针算法
    【题目来源】https://www.acwing.com/problem/content/2076/【题目描述】艾弗里有一个由N个正整数构成的数组。数组中的第i个整数是Ai。如果一个连续的子数组的长度为m,并且按顺序包含整数m,m−1,m−2,…,2,1,则称它为m倒计数。例如,[3,2,1]是3倒计数。请帮助艾......
  • P8704 [蓝桥杯 2020 省 A1] 填空问题 题解
    题目传送门A.跑步训练我们经过仔细观察,可以发现每222分钟就会消耗300300......
  • 线段树——AcWing 245. 你能回答这些问题吗
    目录线段树定义运用情况注意事项解题思路AcWing245.你能回答这些问题吗题目描述运行代码代码思路改进思路线段树定义线段树是一种用于区间查询和更新问题的数据结构。它通过递归地将一个区间分解为若干子区间,每个节点代表一个子区间的和、最小值、最大值等信息,......
  • 拓扑排序——AcWing 164. 可达性统计
    目录拓扑排序定义运用情况注意事项解题思路AcWing164.可达性统计题目描述运行代码代码思路改进思路拓扑排序定义拓扑排序(TopologicalSort)是对有向无环图(DirectedAcyclicGraph,简称DAG)的一种排序方式。在一个有向无环图中,拓扑排序的结果是一个线性的顶点序列,其......
  • 并查集——AcWing 239. 奇偶游戏
    目录并查集定义运用情况注意事项解题思路AcWing239.奇偶游戏题目描述运行代码代码思路改进思路并查集定义并查集(DisjointSetUnion,简称DSU),是一种树形的数据结构,常用于处理一些不交集的合并及查询问题。在并查集中,元素被分成多个不相交的集合,每个集合由一个代表......