C/C++教程

【算法】AcWing 870. 约数个数

本文主要是介绍【算法】AcWing 870. 约数个数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法思想

约束的个数都加一,然后全部乘在一起。
在这里插入图片描述

代码:
学到了unordered_map
因为x在循环过程中会变小,所以可能x还没被完全分解就退出循环了,所以要有if(x>1)那个判断。

#include<iostream>
#include<unordered_map>
#define LL long long int 
using namespace std;

const int MOD=1e9+7;

int main()
{
	int n;cin>>n;
	unordered_map<int,int>a;
	
	while(n--)
	{
		int x;cin>>x;
		
		for(int i=2;i<=x/i;i++)
		{
			while(x%i==0)
			{
				a[i]++;
				x/=i;
			}
		}
		
		//最后一个最大公约数 
		if(x>1) a[x]++;
		
	
	}
	LL ans=1;
	for(auto i:a) ans=ans*(i.second+1)%MOD;
		
	cout<<ans;
	return 0;
}
这篇关于【算法】AcWing 870. 约数个数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!