【CZY选讲·次大公因数】

题目描述

给定n个数ai，求sgcd(a1,a1),sgcd(a1,a2),…,sgcd(a1,an)。

其中sgcd(x,y)表示x和y的次大公因数。若不存在次大公因数，sgcd(x,y)=-1。

数据范围

n<=10^5，ai<=10^12。

题解：

①关键在于快速求出次大公因数。

②次大公因数sgcd=gcd/p p为gcd的最小质因子

③由于每次运算都与a1有关,因此先将a1进行素数分解,得出gcd后枚举a1素因子找到最小的能够整除gcd的即可

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<math.h>

#include<cstring>

#define go(i,a,b) for(int i=a;i<=b;i++)

#define ro(i,a,b) for(int i=a;i>=b;i--)

#define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

int main()

{

    //又是一道口糊的题？

	return 0;

}//czy020202

如今儿时的街道，变成钢筋水泥的欲望丛林。

只有孤独的你我，伴着奇幻壮丽的旷世彷徨…… ————汪峰《流浪》

巴特西

【CZY选讲·次大公因数】

最新文章

热门文章