很显然,每一步所选的剑和怪物都是确定的,可以先求出来(不用写平衡树,直接用multiset即可,注意删除要删指针,以下假设第i次攻击用ki攻击的剑,攻击第i只怪)
 首先判断无解,即如果存在ai使得gcd(ki,pi)不是ai的约数就无解,否则将ki、pi、ai同除gcd(ki,pi),并用扩欧求出ki关于pi的逆元,移到右边
最终相当于求线性方程组的最小正整数解,用EXCRT即可

 1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 100005
4 #define ll long long
5 multiset<ll>s;
6 multiset<ll>::iterator it;
7 int T,n,m;
8 ll x,y,sum,a[N],p[N],t[N];
9 bool flag;
10 ll exgcd(ll a,ll b,ll &x,ll &y){
11 if (!b){
12 x=1;
13 y=0;
14 return a;
15 }
16 ll t=exgcd(b,a%b,y,x);
17 y-=a/b*x;
18 return t;
19 }
20 ll mul(ll a,ll b,ll p){
21 if (!b)return 0;
22 ll s=mul(a,b>>1,p);
23 s=s*2%p;
24 if (b&1)s=(s+a)%p;
25 return s;
26 }
27 int main(){
28 scanf("%d",&T);
29 while (T--){
30 scanf("%d%d",&n,&m);
31 for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
32 for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
33 for(int i=1;i<=n;i++)scanf("%lld",&t[i]);
34 s.clear();
35 for(int i=1;i<=m;i++){
36 scanf("%lld",&x);
37 s.insert(x);
38 }
39 for(int i=1;i<=n;i++){
40 it=s.upper_bound(a[i]);
41 if (it!=s.begin())it--;
42 x=*it;
43 s.erase(it);
44 s.insert(t[i]);
45 t[i]=x;
46 }
47 flag=sum=0;
48 for(int i=1;i<=n;i++){
49 sum=max(sum,(a[i]-1)/t[i]);
50 ll d=exgcd(t[i],p[i],x,y);
51 if (a[i]%d){
52 flag=1;
53 break;
54 }
55 p[i]/=d;
56 a[i]=mul(a[i]/d,(x%p[i]+p[i])%p[i],p[i]);
57 }
58 for(int i=2;i<=n;i++){
59 ll d=exgcd(p[1],p[i],x,y);
60 if (a[1]%d!=a[i]%d){
61 flag=1;
62 break;
63 }
64 p[i]/=d;
65 a[1]+=mul((a[i]-a[1])/d,(x%p[i]+p[i])%p[i],p[i])*p[1];
66 p[1]*=p[i];
67 a[1]=((a[1]%p[1])+p[1])%p[1];
68 }
69 if (flag)printf("-1\n");
70 else
71 if (sum<a[1])printf("%lld\n",a[1]);
72 else printf("%lld\n",a[1]+(sum-a[1]+p[1])/p[1]*p[1]);
73 }
74 }

最新文章

  1. Bootstrap的安装
  2. 甲乙(数理逻辑)转自http://www.cnblogs.com/devymex/p/3329635.html
  3. express-10 表单处理
  4. ecmall二次开发 直接实例化mysql对象
  5. ENVI5.1安装破解教程
  6. delegate-使用笔记
  7. FAB、TextInputLayout及Snackbar笔记
  8. Scrapy爬虫大战京东商城
  9. shader之半兰伯特漫反射
  10. BZOJ_3012_[Usaco2012 Dec]First!_trie树+拓扑排序
  11. php json数据 入库时 转义字符丢失
  12. 黑盒测试实践——day06
  13. 题解-SDOI2015 约数个数和
  14. HRBUST - 1818 石子合并 区间dp入门
  15. jenkins2.0以后的版本提供自动部署和远程部署功能?
  16. Maven 集成Tomcat7插件
  17. 【洛谷P3411】字串变换
  18. 环形缓冲区-模仿linux kfifo【转】
  19. Mongodb是用Sum 和Where条件
  20. Gradle入门实战(Windows版)

热门文章

  1. spoj2 prime1 (区间筛)
  2. v72.01 鸿蒙内核源码分析(Shell解析) | 应用窥伺内核的窗口 | 百篇博客分析OpenHarmony源码
  3. Redis 基础数据类型重温
  4. Python ThreadPoolExecutor 线程池导致内存暴涨
  5. git 更新与图形界面
  6. 设置elementUI的table组件滚动条位置
  7. javascript-jquery的基本方法
  8. DDL_Killer Alpha版本 Bug集中反馈处
  9. seata整合nacos完成分布式的部署
  10. 攻防世界 杂项 11.simple_transfer