先去考虑两个变量的sgcd怎么求……我们先求出他们的gcd，然后在除掉一个最小的质因子即可。

那么我们先把\(a_1\)分解质因数，然后所有数和它求一个gcd，然后去去掉一个尽可能小的质因子。注意到一个数\(p\)的质因子数量是\(O(\log p)\)级别的，所以每一个数找到要除的那个最小的质因子只需要\(O(\log a_1)\)的时间。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
const int maxn = 100005;
using ll = long long;
ll V[maxn]; int vcnt = 0;
void des(ll x) {
  ll m = (ll)sqrt(x + 0.5);
  for(ll i = 2; i <= m; i ++) {
    if(x % i == 0) {
      V[vcnt ++] = i;
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1LL) V[vcnt ++] = x;
}
ll gcd(ll a, ll b) {
  if(!b) return a;
  else return gcd(b, a % b);
}

ll A[maxn];
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]);
  }
  des(A[1]);
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    ll bs = gcd(A[i], A[1]);
    if(bs == 1) {
      printf("-1"); continue;
    }
    for(int j = 0; j < vcnt; j ++) {
      if(A[i] % V[j] == 0) {
        bs /= V[j];
        break;
      }
    }
    printf("%lld", bs);
  }
  puts("");
  return 0;
}

• 相关文章
• 全局相关文章