fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     private static final long MAXN = 1000000;
  5.     private static final long MOD = 1000000007;
  6.     private static long[] spf = new long[(int) MAXN + 1];
  7.  
  8.     private static void computeSPF() {
  9.         for (int i = 2; i <= MAXN; i++) spf[i] = i;
  10.         for (int i = 2; i * i <= MAXN; i++) {
  11.             if (spf[i] == i) {
  12.                 for (int j = i * i; j <= MAXN; j += i) {
  13.                     if (spf[j] == j) spf[j] = i;
  14.                 }
  15.             }
  16.         }
  17.     }
  18.  
  19.     private static Map<Long, Long> factorize(long value) {
  20.         Map<Long, Long> factors = new HashMap<>();
  21.         while (value != 1) {
  22.             long divisor = spf[(int) value];
  23.             factors.put(divisor, factors.getOrDefault(divisor, 0L) + 1);
  24.             value /= divisor;
  25.         }
  26.         return factors;
  27.     }
  28.  
  29.     public static void main(String[] args) {
  30.         Scanner scanner = new Scanner(System.in);
  31.         int n = scanner.nextInt();
  32.         int m = scanner.nextInt();
  33.  
  34.         computeSPF();
  35.  
  36.         Map<Long, Long> b1 = new HashMap<>();
  37.         for (long i = 2; i <= m; i++) {
  38.             Map<Long, Long> factors = factorize(i);
  39.             for (Map.Entry<Long, Long> entry : factors.entrySet()) {
  40.                 b1.put(entry.getKey(), b1.getOrDefault(entry.getKey(), 0L) + entry.getValue());
  41.             }
  42.         }
  43.  
  44.         long[] b = new long[n + 1];
  45.         for (int i = 1; i <= n; i++) {
  46.             b[i] = scanner.nextLong();
  47.  
  48.             Map<Long, Long> b5 = new HashMap<>(b1);
  49.             Map<Long, Long> factors = factorize(b[i]);
  50.  
  51.             for (Map.Entry<Long, Long> entry : factors.entrySet()) {
  52.                 b5.put(entry.getKey(), b5.getOrDefault(entry.getKey(), 0L) + entry.getValue());
  53.             }
  54.  
  55.             long g = 1;
  56.             for (Map.Entry<Long, Long> entry : b5.entrySet()) {
  57.                 g = (g * ((entry.getValue() % MOD + 1) % MOD)) % MOD;
  58.             }
  59.             System.out.print(g + " ");
  60.         }
  61.         scanner.close();
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.16s 65680KB
comments (?)
stdin
copy 
2 3
2 6
stdout
copy 
6 9
https://ideone.com/JZ0nWD
language:
Java (HotSpot 12)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!