代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
const int MAXN = 1e5 + 10;
typedef long long LL;

int n, m;
LL a[MAXN], p[MAXN], pn[MAXN], att[MAXN];
namespace solver1 {
  LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
  LL exgcd(LL a, LL b, LL &x, LL &y) { // a * x + b * y = gcd(a, b)
    if (b == 0) {
      x = 1, y = 0;
      return a;
    } else {
      LL d = exgcd(b, a % b, y, x);
      y -= (a / b) * x;
      return d;
    }
  }
  LL mul(LL a, LL b, LL mod) {
    a = (a % mod + mod) % mod;
    b = (b % mod + mod) % mod;
    LL ans = 0;
    for (; b; b >>= 1, (a += a) >= mod ? a -= mod : a) {
      if (b & 1) (ans += a) >= mod ? ans -= mod : ans;
    }
    return ans;
  }
  LL calc(LL x1, LL p1, LL x2, LL p2) { // CRT
    LL k1, k2;
    LL g = exgcd(p1, p2, k1, k2);
    
    if ((x1 - x2) % g != 0) return -1;

    LL l = p1 / g * p2;
    k1 = mul(k1, (x2 - x1) / g, l);
    k1 = (k1 % l + l) % l;
    LL res = x1 + mul(k1, p1, l);

    return (res % l + l) % l;
  }
  void main() {
    std::multiset<LL> sword;

    static LL use[MAXN];
    for (int i = 1; i <= m; i++) sword.insert(att[i]);

    for (int i = 1; i <= n; i++) {
      std::multiset<LL>::iterator it = sword.upper_bound(a[i]);
      if (it != sword.begin()) {
        --it;
      }

      use[i] = *it;

      sword.erase(it);
      sword.insert(pn[i]);
    }

    LL low = 0;
    for (int i = 1; i <= n; i++) {
      LL t = a[i] / use[i];
      if (t * use[i] < a[i]) t++;
      low = std::max(low, t);
    }

    static LL tmp[MAXN];
    for (int i = 1; i <= n; i++) {
      //calc x
      LL x, y;
      LL g = exgcd(use[i], p[i], x, y);
      if (a[i] % g != 0) {
        puts("-1");
        return;
      }
      tmp[i] = mul(x, (a[i] / g), p[i]);

      p[i] /= g;
      tmp[i] = (tmp[i] % p[i] + p[i]) % p[i];
    }

    LL ans, lcm;
    if (n == 1) {
      ans = tmp[1];
      lcm = p[1];
    } else {
      ans = calc(tmp[1], p[1], tmp[2], p[2]);

      //fprintf(stderr, "!!!\n");
      if (ans == -1) {
        puts("-1");
        return;
      }
      
      lcm = p[1] / gcd(p[1], p[2]) * p[2];

      //if (lcm == 0) { fprintf(stderr, "start! %lld %lld\n", p[1], p[2]); }
      for (int i = 3; i <= n; i++) {
        ans = calc(ans, lcm, tmp[i], p[i]);
        
        if (ans == -1) {
          puts("-1");
          return;
        }
        
        lcm = lcm / gcd(p[i], lcm) * p[i];
        //if (lcm == 0) { fprintf(stderr, "start %d %lld!\n", i, p[i]); }
      }
    }

    //fprintf(stderr, "%lld %lld!\n", low, lcm);
    if (ans < low) { 
      LL delta = (low - ans) / lcm;
      ans += delta * lcm;
      if (ans < low) ans += lcm;
    } else {
      LL delta = (ans - low) / lcm;
      ans -= delta * lcm;
      if (ans < low) ans += lcm;
    }

    printf("%lld\n", ans);
    
  }
}
int main() {
#ifndef LOCAL
  freopen("dragon.in", "r", stdin);
  freopen("dragon.out", "w", stdout);
#endif
  int t;
  scanf("%d", &t);
  while(t--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      scanf("%lld", a + i);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%lld", p + i);
    }
    for (int i = 1; i <= n; i++) {
      scanf("%lld", pn + i);
    }
    for (int i = 1; i <= m; i++) {
      scanf("%lld", att + i);
    }

    solver1::main();
  }
}

评测结果