首页 > 其他分享 >AcWing871. 约数之和

AcWing871. 约数之和

时间:2024-07-24 11:43:23浏览次数:11  
标签:约数 prime int long ai AcWing871 mod

题目链接:https://www.acwing.com/problem/content/description/873/

题目叙述:

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

输入格式

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

输出格式

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

数据范围

1≤n≤100,1≤ai≤2×10^9

输入样例:

3
2
6
8

输出样例:

252

直接上代码

#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 p : prime) {
		int a = p.first;
		int b = p.second;
		long long t = 1;
		while (b--) t = (t * a + 1) % mod;
		res = res * t % mod;
	}
	cout << res;
	return 0;
}

标签:约数,prime,int,long,ai,AcWing871,mod
From: https://www.cnblogs.com/Tomorrowland/p/18320515

相关文章

  • AcWing 870. 约数个数
    题目叙述:题目链接:https://www.acwing.com/video/295/给定n个正整数ai,请你输出这些数的乘积的约数个数,答案对1e9+7取模。输入格式第一行包含整数n。接下来n行,每行包含一个整数ai。输出格式输出一个整数,表示所给正整数的乘积的约数个数,答案需对1e9+7取模。数据范......
  • 洛谷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......
  • 最小公约数与最大公倍数(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......
  • 约数问题(模板)
    869.试除法求约数-AcWing题库#include<bits/stdc++.h>usingnamespacestd;vector<int>solve(intx){vector<int>ans;for(inti=1;i<=x/i;i++){if(x%i==0){ans.push_back(i);if(x/i!=i)a......
  • ..约数..
    先做回顾1、什么是约数?在数学中,一个数的约数(Divisor)是能够整除这个数的所有正整数。换句话说,如果一个正整数 d 能够被另一个正整数 n 整除,那么 d 就是 n 的一个约数。2、算术基本定理——唯一分解定理它指出,每个大于1的自然数都可以唯一地表示为若干个质数的乘积,而......
  • 第K个约数
    题目链接:https://bzoj.org/p/3758Description给你一个数字N,再给个数字K将N的所有约数从小到大排好,求第K个约数,如果不存在输出-1Input一行给出N,KN<=1e15K<=1e9Output如题Samples输入数据142输出数据12当我刚开始看见尝试:7已通过:2难度:10时,有点退缩的......
  • 用质因数求解最大公约数(gcd)和最小公倍数(lcm)
    用质因数求解最大公约数(gcd)思路分析:1、质因数:(素因数或质因子)他指的是能整除给定正整数的质数。例如:36可以分解为223*3,其中2和3就是质因数。2、质因数求解最大公约数:对每个数进行质因数分解;找出所有数的共有质因数,并取每个共有质因数的最低次幂;将这些最低次幂的质因......
  • 3169 找出最大公约数
    解法一:循环倒叙一个个找#include<bits/stdc++.h>#definef(i,s,e)for(inti=s;i<=e;i++)#definelllonglongusingnamespacestd;constintN=1e3+10,inf=0x3f3f3f3f;intmain(){intn,m;cin>>n>>m;for(inti=n;i>=1......