UR #3 核聚变反应强度( gcd )

tags: -分解质因数 , gcd

题目大意

给定\(n\)个数，求\(a_1\)与\(a_i\)次小公约数

分析

易知次小公约数是\(\gcd\)的因数，于是用\(\gcd\)除去它的最小质因子即可。

没有次小公约数的情况是\(\gcd = 1\)，特判一下即可

直接枚举的时间复杂度为\(O(n \sqrt a)\)

由于数据规模较大考虑优化

由于是求\(sgcd(a_1,a_i)\)于是结果一定是\(a_1\)的质因数组成，于是预处理\(a_1\)的质因数，然后每次处理时除去最小的即可，\(10^{12}< 2^{38}\)于是可以知道得到质因数的个数小于\(38\)个，于是时间复杂度就变为了\(O(50n)\)啦！

代码

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define LL long long

#define maxn 100010

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

using namespace std;

int n;

LL ys[40];

LL gcd(LL a, LL b) {

    while (b ^= a ^= b ^= a %= b);

    return a;

}

int main(){

    scanf("%d",&n);

    LL l,tmp;   int tot = 0;

    scanf("%lld", &l);

    tmp = l;

    for (int i = 2; 1ll * i * i <= l ;i ++)

    if (l % i == 0)

    {

        ys[++tot] = i;

        while (l % i == 0) l /= i;

    }

    if (l != 1) ys[++tot] = l;

    l = tmp ;

    if (l != 1) printf("%lld ",l / ys[1]);

      else printf("-1 ");

    rep(i,2,n){

      LL aa;

      scanf("%lld",&aa);

      LL g = gcd(aa,l);

      if (g == 1) printf("-1 ");

      else rep (j,1,tot)

             if (g % ys[j] == 0 )

              {

                printf("%lld ",g / ys[j]);

                break;

              }

    }

    return 0;

}

巴特西

UR #3 核聚变反应强度( gcd )

题目大意

分析

代码

最新文章

热门文章