题目:
1.注意别一输入 p[ i ] 就 a[ i ] %= p[ i ] ,因为在 multiset 里找的时候还需要真实值。
2.注意用 multiset 。并且,因为要 upper_bound( a[ i ] ) ,而 a[ i ] 是一个 long long 类型的,所以即使 multiset 里装的都是 int 类型的,也得开成 long long 的 multiset 。
3.注意除了同余的限制,还有一个是 \( x*c_i >= a_i \) (\(c_i\)就是对应剑的攻击力);只需要在最后用所有 p 的 lcm 调整一下即可。
4.注意要用大数乘法……再各种地方都要注意是否可以直接乘。
别写错扩展 CRT ,特别是 x 乘上 r/g 那个部分。
不太明白为了最后的 x 是最小正整数,是否需要让中间过程中的每个 x 都是最小正整数。
#include#include #include #include #include #define ll long longusing namespace std;ll rdn(){ ll ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}ll Mx(ll a,ll b){ return a>b?a:b;}const int N=1e5+5;int n,m,atk[N]; ll a[N],p[N],lm; bool fg;struct Node{ ll a,p; Node(ll a=0,ll p=0):a(a),p(p) {}};multiset st;//multiset not set!!!!!!ll Mul(ll a,ll b,ll mod){ ll d=(ll)floor((double)a*b/mod+0.5); ll ret=a*b-d*mod; if(ret<0)ret+=mod; return ret;}ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){x=1;y=0;return a;} ll ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret;}void init(){ for(int i=1;i<=n;i++)a[i]=rdn(); for(int i=1;i<=n;i++)p[i]=rdn()/*,a[i]%=p[i]*/;//for set for(int i=1;i<=n;i++)atk[i]=rdn(); st.clear(); lm=0;/ for(int i=1,d;i<=m;i++) d=rdn(),st.insert(d); multiset ::iterator it,it2; ll d,x,y; for(int i=1;i<=n;i++) { it=st.upper_bound(a[i]);///for here not if(it!=st.begin())it--; d=(*it); st.erase(it); st.insert(atk[i]); ll g=exgcd(d,p[i],x,y); a[i]/=g; p[i]/=g; d/=g;/// lm=Mx(lm,(ll)ceil((double)a[i]/d));// a[i]=Mul(a[i],x,p[i]);/// }}Node cal(Node u,Node v){ ll a=u.p, b=v.p, r=v.a-u.a, x,y; ll g=exgcd(a,b,x,y); if(r%g){ fg=1;return Node(0,0);} a/=g; b/=g; r/=g; x=Mul(x,r,b);/// y=a*b*g; x=(u.a+Mul(x,u.p,y))%y; return Node(x,y);}int main(){ freopen("dragon.in","r",stdin); freopen("dragon.out","w",stdout); int T=rdn(); while(T--) { n=rdn();m=rdn(); fg=0; init(); if(fg){puts("-1");continue;} Node cr=Node(a[1],p[1]); if(fg){puts("-1");continue;} for(int i=2;i<=n;i++) { cr=cal(cr,Node(a[i],p[i])); if(fg){ puts("-1");break;} } if(fg)continue; if(cr.a