UOJ 48 次最大公约数

次最大公约数 = gcd / 其中一个数质因数中最小的。

gcd(42,12) = 6;    div(42) = 2*3*7   div(12) = 2^2*3

sgcd(42,12) = 6 / 2 = 3;

之前素数筛选，分解质因数总是找模板，整理后就用红书上的模板了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b)
{
    return b == 0 ? a : gcd(b,a%b);
}

ll a[100005];

int tot;
ll primes[100005];
int num_primes[100005];
void divide(ll x)
{
    ll tmp = (int)(double(sqrt(x))+1);
    tot = 0;
    ll now = x;

    for(ll i=2; i<=tmp; i++) {
        if(now%i==0)
        {
            primes[++tot] = i;
            num_primes[tot] = 0;
            while(now%i==0)
            {
                ++num_primes[tot];
                now/=i;
            }
        }
    }

    if(now!=1)
    {
        primes[++tot] = now;
        num_primes[tot] = 1;
    }

}

int main()
{
    int n;
    scanf("%d",&n);

    for(int i=0; i<n; i++)
        scanf("%lld",&a[i]);

    divide(a[0]);

    for(int i=0; i<n; i++)
    {
        ll g = gcd(a[0],a[i]);
        ll tmp = g;
        for(int j=1; j<=tot; j++)
        {
            if(tmp%primes[j]==0)
            {
                tmp = tmp / primes[j];
                break;
            }
        }
        if(tmp==g)
            printf("%d ",-1);
        else printf("%lld ",tmp);
    }


    return 0;
}