\u5f85\u8865\u9898\u89e3\u3002<\/p>\n\n\n\n\n\n\n\n
#pragma comment(linker, \"\/stack:200000000\")\n#pragma GCC optimize(\"Ofast,no-stack-protector\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native\")\n#pragma GCC optimize(\"unroll-loops\")\n#include <bits\/stdc++.h>\n\n\nusing namespace std;\ntypedef long long ll;\n#define set0(x) memset(x,0,sizeof(x))\n#define F first\n#define S second\n#define PB push_back\n#define MP make_pair\n#define rep(i, a, b) for(int i = a; i < (b); ++i)\n#define trav(a, x) for(auto& a : x)\n#define all(x) x.begin(), x.end()\n#define sz(x) (int)(x).size()\n\nll chkmax(ll &a,ll b){return a = a>b?a:b;}\ntypedef long long ll;\ntypedef pair<int,int> pii;\ntypedef pair<ll,ll> pll;\ntypedef vector<int> VI;\ntemplate<typename T> void read(T &x){\n\tx = 0;char ch = getchar();ll f = 1;\n\twhile(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}\n\twhile(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;\n}\ntemplate<typename T, typename... Args> void read(T &first, Args& ... args) {\n\tread(first);\n\tread(args...);\n}\n\nll euclid(ll a, ll b, ll &x, ll &y) {\n\tif (b) { ll d = euclid(b, a % b, y, x);\n\t\treturn y -= a\/b * x, d; }\n\treturn x = 1, y = 0, a;\n}\n\n__int128_t crt(__int128_t a, __int128_t m, __int128_t b, __int128_t n) {\n\tif (n > m) swap(a, b), swap(m, n);\n\tll cx,cy,g = euclid(m, n, cx, cy);\n\t__int128_t x = cx,y = cy;\n\tif(!((a - b) % g == 0))return -1;\n\tx = (b - a) % n * x % n \/ g * m + a;\n\treturn x < 0 ? x + m*n\/g : x;\n}\n\nll mul(ll a,ll b,ll c){\n\treturn (ll)(__int128_t(a)*b%c);\n}\nll T;\nint main() {\n\tread(T);\n\twhile(T--){\n\t\tint n,m;\n\t\tll cu,lwb = 0,ma,mm;\n\t\tmultiset<ll> Se;\n\t\tread(n,m);\n\t\tvector<ll> a(n+1),p(n+1),aw(n+1),u(n+1),req(n+1),md(n+1);\n\t\tfor(int i=1;i<=n;i++)read(a[i]);\n\t\tfor(int i=1;i<=n;i++)read(p[i]);\n\t\tfor(int i=1;i<=n;i++)read(aw[i]);\n\t\tfor(int i=1;i<=m;i++){\n\t\t\tread(cu);\n\t\t\tSe.insert(cu);\n\t\t}\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tauto it = Se.upper_bound(a[i]);\n\t\t\tif(*it != *Se.begin())it--;\n\t\t\tu[i] = *it;\n\t\t\tSe.erase(Se.find(*it));\n\t\t\tSe.insert(aw[i]);\n\t\t}\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tlwb = max(lwb,(a[i]+u[i]-1)\/u[i]);\n\t\t\tll x,y,d = euclid(u[i]%p[i],p[i],x,y),cr = a[i]%p[i];\n\t\t\tif(cr%d == 0){\n\t\t\t\tmd[i] = p[i]\/d;\n\t\t\t\tx = (x%md[i])+md[i];\n\t\t\t\treq[i] = mul(x,cr\/d,md[i]);\n\t\t\t}else goto fail;\n\t\t}\n\t\tma = 0;\n\t\tmm = 1;\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tma = crt(ma,mm,req[i],md[i]);\n\t\t\tif(ma == -1){\n\t\t\t\tgoto fail;\n\t\t\t}\n\t\t\tmm = mm*(md[i]\/__gcd(mm,md[i]));\n\t\t}\n\t\tcout<<mm*((lwb-ma+mm-1)\/mm)+ma<<endl;\n\t\tcontinue;\n\t\tfail:;\n\t\tcout<<-1<<endl;\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"\u5f85\u8865\u9898\u89e3\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/359"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=359"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/359\/revisions"}],"predecessor-version":[{"id":360,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/359\/revisions\/360"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=359"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=359"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}