3377. 约数的个数(约数个数)

https://www.acwing.com/problem/content/3380/

这题和第11届蓝桥杯B组国赛题类似

数论知识,就是分解质因数,把质数的指数加1即可

需要注意的是,本题应该是不能用数组模拟的,空间太少了

可以用unordered_map存储

#include<iostream>
#include<cstdio>
#include<cstring>
#include<unordered_map>

using namespace std;

unordered_map<int,int>primes;

int t;

void divide(int n)
{
	for (int i = 2; i <= n / i; i++)
	{
		if (n % i == 0)
		{
			int s = 0;
			while (n % i == 0)
			{
				n /= i;
				s++;
			}
			primes[i] = s;
		}
	}
	if (n > 1)
	{
		primes[n] = 1;
	}
}

int main()
{
	cin >> t;
	while(t--)
	{
		primes.clear();
		int num;
		cin >> num;
		divide(num);
		long long sum=1;
		for(auto p:primes)sum*=p.second+1;
		cout << sum << endl;
	}
}