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
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;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！