2-试除法求约数&约数个数&约数和

算法思想

约数个数定理_百度百科约数和定理_百度百科

算法模板

约数和

import java.util.*;

public class Main {
    static int N = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Map<Integer, Integer> map = new HashMap<>();

        while(n -- > 0)
        {
            int x = in.nextInt();
            for(int i = 2; i <= x / i; i ++ )
            {
                while(x % i == 0)
                {
                    x /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }

            if(x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
        }

        long res = 1;
        for(Map.Entry<Integer, Integer> entry : map.entrySet())
        {
            int p = entry.getKey();
            int r = entry.getValue();
            long t = 1;

            while(r -- > 0) t = (t * p + 1) % N;
            res = res * t % N; 
        }

        System.out.println(res);
    }
}

参考资料

1. 公式推导：约数和定理，约数个数定理