NOI2018 屠龙勇士

multiset 预处理出击杀每条龙的剑的攻击力,然后 EXCRT 即可。

#include <iostream>
#include <cstdio>
#include <set>

typedef long long LL;
#define int LL

const int MAXN = 1e5;

int n, m, T;
int a[MAXN | 1], p[MAXN | 1], dragon_swo[MAXN | 1], swo[MAXN | 1], dragon_use[MAXN | 1];
std::multiset < int > set;

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

void out(int x) {
  if (!x) return;
  out(x / 10);
  putchar(x % 10 + '0');
}

namespace solve1 {
  void MAIN() {
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = std::max(ans, (a[i] - 1) / dragon_use[i] + 1);
    out(ans);
    printf("\n");
  }
}

int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = exgcd(b, a % b, y, x);
  y -= (a / b) * x;
  return d;
}

int LCM(int x, int y) {
  int a, b;
  return x / exgcd(x, y, a, b) * y;
}

namespace solve2 {
  LL mul(LL x, LL y, LL p) {
    LL res = 0, base = x % p;
    while (y > 0) {
      if (y & 1) res = (res + base) % p;
      base = (base + base) % p;
      y >>= 1;
    }
    return res;
  }
  void MAIN() {
    LL lcm = 1;
    LL res = 0;
    for (int i = 1; i <= n; ++i) {
      LL x, y;
      LL gcd = exgcd(mul(lcm, dragon_use[i], p[i]), p[i], x, y);
      LL right = (a[i] - mul(dragon_use[i], res, p[i]) + p[i]) % p[i];
      if (right % gcd != 0) {
        printf("-1\n");
        return;
      }
      x = mul(x, right / gcd, p[i] / gcd) + p[i] / gcd;
      res = (res + x * lcm);
      lcm = lcm * p[i] / exgcd(p[i], dragon_use[i] * lcm, x, y);
      // lcm = LCM(lcm, p[i] / exgcd(p[i], dragon_use[i] * lcm, x, y));
      res = (res + lcm) % lcm;
    }
    out(res);
    printf("\n");
  }
}

signed main() {
  T = read();
  while (T--) {
    set.clear();
    n = read();
    m = read();
    bool flag = false;
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) {
      p[i] = read(); 
      if (p[i] != 1) flag = true;
    }
    for (int i = 1; i <= n; ++i) dragon_swo[i] = read();
    for (int i = 1; i <= m; ++i) swo[i] = read();
    for (int i = 1; i <= m; ++i) set.insert(swo[i]);
    for (int i = 1; i <= n; ++i) {
      std::multiset < int > :: iterator it = set.upper_bound(a[i]);
      if (it != set.begin()) --it;
      dragon_use[i] = *it;
      set.erase(it);
      set.insert(dragon_swo[i]);
    }
    if (!flag) solve1::MAIN();
    else solve2::MAIN();
  }
  return 0;
}
最后修改:2019 年 09 月 21 日 10 : 16 AM

发表评论