朔州城市建设网站,网页设计需要学什么专业陪护工,网站后台模板 如何使用,网站建设需要哪些材料正题
题目链接:https://www.luogu.com.cn/problem/P4774 题目大意 nnn个龙血量为aia_iai#xff0c;回复能力为pip_ipi#xff0c;死亡后掉落剑的攻击力tit_iti#xff0c;mmm把剑#xff0c;攻击力为bib_ibi。
从111开始打#xff0c;每次使用不大于当前龙血量…正题
题目链接:https://www.luogu.com.cn/problem/P4774 题目大意
nnn个龙血量为aia_iai回复能力为pip_ipi死亡后掉落剑的攻击力tit_itimmm把剑攻击力为bib_ibi。
从111开始打每次使用不大于当前龙血量的剑中攻击力最低的一把没有就用攻击力最低的造成x×atkx\times atkx×atk点伤害然后当前的剑坏掉。
求一个最小的xxx使得所有龙被攻击后血量是pip_ipi的倍数。
1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105满足p1p1p1或者ai≤pia_i\leq p_iai≤pi所有pip_ipi的公倍数不超过101210^{12}1012 解题思路
额先用setsetset处理出每个龙用哪把剑打cic_ici然后就是对于每条龙的条件就是 cix≡ai(modpi),cix≥aic_ix\equiv a_i(mod\ p_i),c_ix\geq a_icix≡ai(mod pi),cix≥ai 后面那个条件可以去掉我们先求出满足所有cix≥aic_ix\geq a_icix≥ai的最小xxx后面再调整。
然后前面那个东西可以用EXCRTEXCRTEXCRT搞了假设我们上一次求到的答案为ansansans目前pip_ipi的公倍数是MMM那么现在的通解就是ansMxansMxansMx。我们需要求出一个xxx满足 ci(ansMx)≡ai(modpi)c_i(ansMx)\equiv a_i(mod\ p_i)ci(ansMx)≡ai(mod pi) ⇒Mxpiyai−ci×ans\Rightarrow Mxp_iya_i-c_i\times ans⇒Mxpiyai−ci×ans 然后就可以扩欧合并了。 code
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includeset
#define ll __int128
using namespace std;
ll read(){ll x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
void print(ll x)
{if(x9)print(x/10);putchar(x%1048);return;}
const ll N1e510;
multisetll s;
ll n,m,T,a[N],p[N],t[N],c[N];
ll exgcd(ll a,ll b,ll x,ll y){if(!b){x1;y0;return a;}ll dexgcd(b,a%b,x,y);ll zx;xy;yz-a/b*y;return d;
}
void work(){nread();mread();s.clear();ll mx0;for(ll i1;in;i)a[i]read();for(ll i1;in;i)p[i]read();for(ll i1;in;i)t[i]read();for(ll i1;im;i){ll xread();s.insert(x);}for(ll i1;in;i){multisetll::iterator it;if(a[i]*s.begin())its.begin();else it--s.upper_bound(a[i]);c[i]*it;s.erase(it);s.insert(t[i]);mxmax(mx,(a[i]-1)/c[i]1);}ll M1,x,y,ans0;for(ll i1;in;i){ll dexgcd(M*c[i],p[i],x,y);ll wa[i]-c[i]*ans,vp[i]/d;if(w%d){puts(-1);return;}xw/d*x%v;ansansx*M;MM*v;ans(ans%MM)%M;}if(ansmx)ans(mx-ansM-1)/M*M;print(ans);putchar(\n);
}
signed main()
{scanf(%lld,T);while(T--){work();}return 0;
}
