AcWing 870. 约数个数
原题链接
简单
作者:
当下LYC
,
2024-01-28 11:24:40
,
所有人可见
,
阅读 35
算法1
c++代码
//求约数个数,首先知道任何一个整数可以分解成N = p1^a1 * p2^a2 * p3^a3 * ... * pn^an;
//任何一个约数又可以分解为 : p1^b1 * p2^b2 * p3^b3 * ... * pn^bn;
//一个数因式分解的结果可以被任意一个因式子所影响,而不同的个数就是从0~a1这些数,
//那么也就是(a1 + 1) * (a2 + 1) * ... * (an + 1);
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int mod =1e9 + 7;
typedef long long ll;
int main()
{
int n; scanf("%d",&n);
unordered_map<int , int> primes;//map里面应该有两个数:一个是a,一个是primes函数值.
while(n--)
{
int a;scanf("%d",&a);
for(int i = 2 ; i <= a / i ; i++)
{
while(a % i == 0){
a/=i;
primes[i]++;
}
}
if(a > 1) primes[a]++;//如果a足够大的话
}
ll res = 1;
for(auto p : primes) res = res * (p.second + 1) % mod;
cout << res << endl;
}
算法2
Java 代码
import java.util.*;
public class Main{
static int mod = (int)1e9 + 7;//之所以是这个数,是因为这是离1e9最近的质数,用这样的数更不容易重复(数学上有证明)
public static void main(String[] args){
Map<Integer,Integer> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n-- != 0){
int a = sc.nextInt();
for(int i = 2; i <= a / i ; i++){
while(a % i == 0){
a/=i;
map.put(i,map.getOrDefault(i,0) + 1);
}
}
if(a > 1) map.put(a,map.getOrDefault(a,0) + 1);
}
long res = 1;
for(int key : map.values()){
res = res * (key + 1) % mod;
}
System.out.println(res);
}
}