约数个数
题目 约数个数
思路分析
首先还是想暴力 把最后的数算出来 然后用试除法求得约数在set里 最后取出set的size就是答案
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
set<int> get_divisors(int n){
set<int> res;
for(int i=1;i<=n/i;i++){
if(n%i==0){
res.insert(i);
res.insert(n/i);
}
}
return res;
}
int main()
{
int n;cin>>n;
long long sum=1;
while(n--){
int a;cin>>a;
sum*=a; cout<<"sum "<<sum<<endl;
}
auto res=get_divisors(sum);
cout<<res.size()%mod;
return 0;
}
这里用的是相乘 先抛开时间不说 都找不到一个合适的数据类型存放最终的数
第三组数据就爆了 还是long long
学习一个新思路
类似于排列问题
一个数的约数是由这个数的几个质因子相乘得到的
例如：12 的质因子有 2，3
12的约数有：1，2，3，4，6，12
约数1 是由 0 个 2， 0 个3相乘得到的
约数2 是由 1 个 2， 0 个3相乘得到的
约数3 是由 0 个 2， 1 个3相乘得到的
约数4 是由 2 个 2， 0 个3相乘得到的
约数6 是由 1 个 2， 1 个3相乘得到的
约数12 是由 2 个 2， 1 个3相乘得到的
12 可以分解为：2^2*3^1
所以
2可以取 0 ~ 2个，3种取法
3可以取 0~1 个，2种取法
12的约数一共：2 * 3 = 6个
也就是：
把一个数N 写成：N = (p1^x1)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数。
则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)
那么问题转变成 把每个数 分解质因数出来 把每个质因数（基数）出现的次数（指数）累加起来
最后再使用每个基数的指数统一进行计算
显然可以用哈希表
代码实现
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
unordered_map<int,int> Weight;
int T;
int main()
{
cin>>T;
while(T--){
int n;cin>>n;
for(int i=2;i<=n/i;i++){
while(n%i==0){
Weight[i]++;
n/=i;
}
}
if(n>1)
Weight[n]++;
}
long long res=1;
for(auto x:Weight){
res=res*(x.second+1)%mod;
}
cout<<res;
return 0;
}
💬 评论