C++ 均分质因数

题目

There are N integers a 1 , a 2 , . . . , a N not less than 1 The values of a 1 , a 2 , . . . , a N are not known, but it is knownthat a 1 × a 2 × . . . × a N= P

Find the maximum possible greatest common divisor of a 1 , a 2 , . … , a N

简单说一下 就是一个数P等于N个数相乘 求这N个数的最大公因数 这N个数均大于等于一 且为整数
1<=P,N<=10¹²

解决思路：将一个数拆分出他的质因数 通过质因数的分配得出他的结果

例如:N=3 P=2³ * 3⁴ * 5²=16200

因为P的质因数包括3个2相乘 所以我们可以给每个 ai分配一个2
即 a1=2*x1 a2=2*x2 a3=2*x3
同理 3 a1=2*3*x1 a2=2*3*x2 a3=2*3*3*x3
5因为不够分 所以只有两个数可以分配
即 a1=2*3 a2=2*3*5 a3=2*3*3*5*5
所以显然易见 结果为2*3

answer:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;



int main()
{
	ll n,p;
	scanf("%lld%lld",&n,&p);
	if(n==1){
		printf("%lld",p);
		return 0;
	}
	ll ans=1;
	for(ll i=2;i*i<=p;i++)
	{
		ll cnt=0;
		if(p%i==0)
		{
			while(p%i==0)
			{
				cnt++;
				p=p/i;
			}
			int k=cnt/n;
			while(k--) ans=ans*i;
		}
	}
	cout<<ans; 
	 return 0;
	} 
 

最后

以上就是平淡皮皮虾为你收集整理的C++ 均分质因数的全部内容，希望文章能够帮你解决C++ 均分质因数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。