admin管理员组文章数量:1613760
We should know about the Fundamental Theorem of Arithmetic
And we can get the number of the divisors by multipling (α1 + 1) * (α2 + 1) * … * (αN + 1).Basic of Principle of Multiplication.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
static int mod = (int) (1e9 + 7);
static long sum = 1;
static Map<Long, Integer> map = new HashMap<>();
public static void main(String[] args) throws IOException {
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
while (n-- > 0) {
s = br.readLine().split(" ");
sum = Integer.parseInt(s[0]);
for (int i = 2; i <= sum / i; i++)
while (sum % i == 0) {
map.put((long)i, map.getOrDefault((long)i, 0) + 1);
sum /= i;
}
if (sum != 1) map.put(sum, map.getOrDefault(sum, 0) + 1);
}
long res = 1;
for (Map.Entry<Long, Integer> entry : map.entrySet()) res = res * (entry.getValue() + 1) % mod;
pw.println(res);
pw.flush();
br.close();
}
}
本文标签: NumberacwingDivisorsarithmetictheorem
版权声明:本文标题:AcWing 870.Number of Divisors (Fundamental Theorem of Arithmetic) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728643570a1167410.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论