约数个数
给定 n 个正整数 ai,请你输出这些数的乘积的约数个数,答案对 109+7
取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数个数,答案需对 109+7取模。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例:
3 2 6 8
输出样例:
12
算法思路
主要是需要知道公式
提交代码
C++
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1e9 + 7; int main() { int n; cin >> n; unordered_map<int, int> m; while(n --) { int t; cin >> t; for (int i = 2; i <= t / i; ++ i) { while(t % i == 0) { t /= i, m[i] ++; } } if (t > 1) m[t] ++; } LL res = 1; for (auto x : m) res = res * (x.second + 1) % mod; cout << res << endl; return 0; }
Java
import java.util.*; import java.io.*; public class Main { public static void main(String [] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(reader.readLine()); Map<Integer, Integer> m = new HashMap<Integer, Integer>(); // m中存储的是乘积质因分解之后的所有质数,和其对应的个数 while(n -- > 0) { int cur = Integer.parseInt(reader.readLine()); for (int i = 2; i <= cur / i; ++ i) { int cnt = 0; while(cur % i == 0) // 对每一个数进行质因分解 { cnt ++; cur /= i; } m.put(i, m.getOrDefault(i, 0) + cnt); } if (cur > 1) m.put(cur, m.getOrDefault(cur, 0) + 1); // 如果最后这个数没有成为1 那么代表这个数剩下的部也是也给质数 // 也算一个 } long res = 1l; // 这里就是公式的应用 for (Integer cur : m.keySet()) res = res * (m.get(cur) + 1) % ((int)1e9 + 7); System.out.println(res); } }