[UOJ 48][UR #3]核聚变反应堆

danihao123 posted @ 2018年4月24日 14:03 in 题解 with tags UOJ 数论 , 109 阅读
转载请注明出处:http://danihao123.is-programmer.com/

先去考虑两个变量的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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter