算法基础之约数个数

约数个数

• 核心思想：

  • 用哈希表存每个质因数的指数 然后套公式

  •   #include <iostream>#include <algorithm>#include <unordered_map>#include <vector>using namespace std;const int N =110 , mod = 1e9 + 7;typedef long long LL;  //long long 储存int main(){int n;cin>>n;unordered_map<int, int> primes;  while(n--){int x;cin>>x;for(int i = 2;i<= x / i; i++)  //从2开始找质数{while(x % i ==0)  //求指数 while循环{x /= i;primes[i] ++;}}if(x > 1) primes[x] ++;}LL res = 1;for (auto p : primes) res = res * (p.second + 1) % mod;  //哈希表取出来是vectorcout << res << endl;}