青蛙的约会
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 133470 | Accepted: 29610 |
Description
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
Output
Sample Input
1 2 3 4 5
Sample Output
4
Source
分析
设(a=m-n,b=y-x)，那么要解决的方程是
那么exgcd就行了，时间复杂度log级别。
#include<iostream>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
ll exgcd(ll a,ll b,ll&x,ll&y){
if(!b) return x=1,y=0,a;
ll g=exgcd(b,a%b,y,x);
return y-=a/b*x,g;
}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
ll x,y,m,n,l;
read(x),read(y),read(m),read(n),read(l);
ll a=m-n,b=y-x;
if(a<0) a=-a,b=-b;
ll g=exgcd(a,l,x,y);
if(b%g) return puts("Impossible"),0;
ll ans=x*(b/g);
printf("%lld
",(ans%(l/g)+l/g)%(l/g));
return 0;
}
「NOI2018」屠龙勇士
题目描述
小D 最近在网上发现了一款小游戏。游戏的规则如下：
-
游戏的目标是按照编号$1 ightarrow n$ 顺序杀掉$n$ 条巨龙，每条巨龙拥有一个初始的生命值$a_i$ 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $p_i$ ，直至生命值非负。只有在攻击结束后且当生命值恰好为 $0$ 时它才会死去。
-
游戏开始时玩家拥有$m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一 把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。 小D 觉得这款游戏十分无聊，但最快通关的玩家可以获得ION2018 的参赛资格， 于是小D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
-
每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
-
机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的$x$ 次，使巨龙的生命值减少$x imes ATK$ 。
-
之后，巨龙会不断使用恢复能力，每次恢复$p_i$ 生命值。若在使用恢复能力前或某一次恢复后其生命值为$0$ ，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数$x$ 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出$-1$ 即可。
输入输出格式
输入格式：从文件dragon.in 中读入数据。
第一行一个整数T ，代表数据组数。
接下来T 组数据，每组数据包含$5$ 行。
-
每组数据的第一行包含两个整数，$n$ 和$m$ ，代表巨龙的数量和初始剑的数量;
-
接下来一行包含$n$ 个正整数，第$i$ 个数表示第$i$ 条巨龙的初始生命值$a_i$ ;
-
接下来一行包含$n$ 个正整数，第$i$ 个数表示第$i$ 条巨龙的恢复能力$p_i$ ;
-
接下来一行包含$n$ 个正整数，第$i$ 个数表示杀死第$i$ 条巨龙后奖励的剑的攻击力;
-
接下来一行包含$m$ 个正整数，表示初始拥有的$m$ 把剑的攻击力。
输出到文件dragon.out 中。 一共$T$ 行。
第$i$ 行一个整数，表示对于第$i$ 组数据，能够使得机器人通关游戏的最小攻击次数$x$ ，如果答案不存在，输出$-1$。
输入输出样例
说明
第一组数据：
-
开始时拥有的剑的攻击力为${1,9,10}$，第$1$ 条龙生命值为$3$，故选择攻击力为$1$的剑，攻击$59$ 次，造成$59$ 点伤害，此时龙的生命值为$-56$，恢复14 次后生命值恰好为$0$，死亡。
-
攻击力为$1$ 的剑消失，拾取一把攻击力为$7$ 的剑，此时拥有的剑的攻击力为 ${7,9,10}$，第2 条龙生命值为$5$，故选择攻击力为$7$ 的剑，攻击$59$ 次，造成$413$点伤害，此时龙的生命值为$-408$，恢复$68$ 次后生命值恰好为$0$，死亡。
-
此时拥有的剑的攻击力为${3,9,10}$，第$3$ 条龙生命值为$7$，故选择攻击力为$3$ 的剑，攻击$59$ 次，造成$177$ 点伤害，此时龙的生命值为$-170$，恢复$17$ 次后生命值恰好为0，死亡。
-
没有比$59$ 次更少的通关方法，故答案为$59$。
第二组数据： 不存在既能杀死第一条龙又能杀死第二条龙的方法，故无法通关，输出$-1$。
【子任务】
| 测试点编号 | $n$ | $m$ | $p_i$ | $a_i$ | 攻击力 | 其他限制 |
|---|---|---|---|---|---|---|
| 1 | $le 10^5$ | $=1$ | $=1$ | $le 10^5$ | $=1$ | 无 |
| 2 | $le 10^5$ | $=1$ | $=1$ | $le 10^5$ | $=1$ | 无 |
| 3 | $le 10^5$ | $=1$ | $=1$ | $le 10^5$ | $le 10^5$ | 无 |
| 4 | $le 10^5$ | $=1$ | $=1$ | $le 10^5$ | $le 10^5$ | 无 |
| 5 | $le 10^3$ | $le 10^3$ | $le 10^5$ | $le 10^5$ | $le 10^5$ | 特性 1、特性 2 |
| 6 | $le 10^3$ | $le 10^3$ | $le 10^5$ | $le 10^5$ | $le 10^5$ | 特性 1、特性 2 |
| 7 | $le 10^3$ | $le 10^3$ | $le 10^5$ | $le 10^5$ | $le 10^5$ | 特性 1、特性 2 |
| 8 | $=1$ | $=1$ | $le 10^8$ | $le 10^8$ | $le 10^6$ | 特性 1 |
| 9 | $=1$ | $=1$ | $le 10^8$ | $le 10^8$ | $le 10^6$ | 特性 1 |
| 10 | $=1$ | $=1$ | $le 10^8$ | $le 10^8$ | $le 10^6$ | 特性 1 |
| 11 | $=1$ | $=1$ | $le 10^8$ | $le 10^8$ | $le 10^6$ | 特性 1 |
| 12 | $=1$ | $=1$ | $le 10^8$ | $le 10^8$ | $le 10^6$ | 特性 1 |
| 13 | $=1$ | $=1$ | $le 10^8$ | $le 10^8$ | $le 10^6$ | 特性 1 |
| 14 | $=10^5$ | $=10^5$ | $=1$ | $le 10^8$ | $le 10^6$ | 无特殊限制 |
| 15 | $=10^5$ | $=10^5$ | $=1$ | $le 10^8$ | $le 10^6$ | 无特殊限制 |
| 16 | $le 10^5$ | $le 10^5$ | 所有 $p_i$ 是质数 | $le 10^{12}$ | $le 10^6$ | 特性 1 |
| 17 | $le 10^5$ | $le 10^5$ | 所有 $p_i$ 是质数 | $le 10^{12}$ | $le 10^6$ | 特性 1 |
| 18 | $le 10^5$ | $le 10^5$ | 无特殊限制 | $le 10^{12}$ | $le 10^6$ | 特性 1 |
| 19 | $le 10^5$ | $le 10^5$ | 无特殊限制 | $le 10^{12}$ | $le 10^6$ | 特性 1 |
| 20 | $le 10^5$ | $le 10^5$ | 无特殊限制 | $le 10^{12}$ | $le 10^6$ | 特性 1 |
特性 1 是指：对于任意的 $i$，$a_i le p_i$。
特性 2 是指：$operatorname{lcm}(p_i) le 10^6$，即所有 $p_i$ 的最小公倍数不大于 $10^6$。
对于所有的测试点，$T le 5$，所有武器的攻击力 $le 10^6$，所有 $p_i$ 的最小公倍数 $le 10^{12}$。
保证 $ T, n, m $ 均为正整数。
【提示】
你所用到的中间结果可能很大，注意保存中间结果的变量类型。
题解
仔细阅读发现给每条龙的剑的攻击力是固定的，直接用multiset维护即可。
然后就是要求形如(atk_i*x+p_i*y=a_i)的方程组的最小解。
联想到EXCRT解的方程组的形式(xequiv a_i (mod p_i))，和线性同余方程(ax+by=c)的通解的形式(x=frac{c}{d}x_0+tfrac{b}{d},d=gcd(a,b))，
那么这种方程组的解(x=frac{a_i}{d}x_0+tfrac{p_i}{d},d=gcd(atk_i,p_i))可以看成同余式(xequiv frac{a_i}{d}x_0 (mod frac{p_i}{d}))，然后这就变成了EXCRT解决的问题。
然后推程序里面处理的式子，比较繁琐，没什么意义，不写了。
要注意(a_i>p_i)的情况，取模后相当于(a_i)变小了，这样会导致(x)的解变小。所以要注意(xgeqlceilfrac a k ceil)。可以求出(max{lceilfrac a k ceil})，如果最后总方程的(c)小于它，则要补至满足条件的最小值，用式子写一下大概是(c+mlceilfrac{max-c}{m} ceil)。
注意数据范围，会爆long long的地方用快速乘。注意处理负数。
时间复杂度(O(nlog n))
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=1e5+1;
ll a[N],p[N],b[N],X,Y,G;
multiset<ll> s;
multiset<ll>::iterator it;
void exgcd(ll a,ll b){
if(!b) {
X=1,Y=0,G=a;
return;
}
exgcd(b,a%b);
int t=X;X=Y,Y=t-(a/b)*Y;
}
ll mul(ll b,ll k,ll m){
ll a=0;
for(;k;k>>=1,b=(b<<1)%m)
if(k&1) a=(a+b)%m;
return a;
}
void dragon(){
ll n=read<ll>(),m=read<ll>();
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=n;++i) read(p[i]);
for(int i=1;i<=n;++i) read(b[i]);
s.clear();
for(int i=1;i<=m;++i) s.insert(read<ll>());
ll mx=0,c=0;m=1;
for(int i=1;i<=n;++i){
it=s.upper_bound(a[i]);
if(it!=s.begin()) --it;
ll k=*it;s.erase(it),s.insert(b[i]);
mx=max(mx,(a[i]-1)/k+1);
k%=p[i],a[i]%=p[i];
if(!k&&a[i]) return puts("-1"),void();
if(!k&&!a[i]) continue;
exgcd(k,p[i]);
if(a[i]%G) return puts("-1"),void();
p[i]/=G,a[i]=mul(a[i]/G,(X%p[i]+p[i])%p[i],p[i]);
exgcd(m,p[i]);
if((a[i]-c)%G) return puts("-1"),void();
m=m/G*p[i],c=(c+mul(mul(m/p[i],((a[i]-c)%m+m)%m,m),(X%m+m)%m,m))%m;
}
printf("%lld
",c>=mx?c:c+m*(mx-c-1)/m+1);
}
int main(){
freopen("dragon.in","r",stdin),freopen("dragon.out","w",stdout);
for(int t=read<int>();t--;) dragon();
return 0;
}