4397: 【入门】乘积的约数个数(2138)
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:2
解决:2
题目描述
给定 个正整数 ,请你输出这些数的乘积的约数个数,答案对 取余数。
输入
第一行包含整数 。
接下来 行,每行包含一个整数 。
数据范围:
输出
输出一个整数,表示所给正整数的乘积的约数个数。
样例输入 复制
5
3
2
4
18
11
样例输出 复制
40
提示

#include<bits/stdc++.h> using namespace std; /* 因数个数=(a1+1)*(a2+1)*(a3+1)*......*(ai+1) 1. 所有的数相乘,分解质因子,得到质因子及个数 和每个数单独分解质因子,得到质因子及个数,答案一致 2. 每个数相加的结果%10000,和两个数%10000相加,再%10000,结果一致 3. 乘法同理 本题的思路: 将每个数分解质因子,求出每个质因子出现的次数,按公式求解约数个数 */ int n,x; map<int,int> m; map<int,int>::iterator it; typedef long long LL; const int M=1e9+7; LL r=1; int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>x; //分解x的质因子 for(int j=2;j<=sqrt(x);j++){ while(x%j==0){ m[j]++; x=x/j; } } if(x>1) m[x]++; } for(it=m.begin();it!=m.end();it++) { r=r*(it->second+1)%M; } cout<<r; return 0; }