Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
UOJ#396. 【NOI2018】屠龙勇士
? 解题记录 ?
? UOJ ?
? 中国剩余定理 ?
? 扩展欧几里得 ?
2018-09-16 09:39:49
444
0
0
rockdu
? 解题记录 ?
? UOJ ?
? 中国剩余定理 ?
? 扩展欧几里得 ?
http://uoj.ac/problem/396 ## 一、一些小处理 首先,每一条龙该使用哪一把剑是严格确定的,这个可以用set加lower_bound预处理出来。我们发现,要想打死一条龙,需要满足的条件是: $$ atk_ix\equiv hp_i(mod\ p_i) 且 atk_ix \geq hp_i $$ 其中$atk_i$是预处理出的攻击力,$hp_i$是巨龙的血量,$p_i$是恢复能力。 对于后面的限制是好做的,只要求出前面同余方程组的解就可以解出满足后面性质的最小解。 对于前面形如$ax\equiv c(mod\ p) $的方程,我们用扩展欧几里得对$x$求解并用模意义表示解集。 具体地说: $$ax \equiv c (mod\ p) \to ax+py=c$$ 我们解出的解集形如:$x=x_0 \pm k\frac{p}{gcd(a,p)}$ 进而表示为:$x\equiv x_0 (mod\ \frac{p}{gcd(a,p)})$ 现在的问题变成了有多个形如$x\equiv c_i(mod\ p_i)$的同余方程,求他们的共解。 建议把$ax\equiv c(mod\ p) \to x\equiv c_i(mod\ p_i)$写成一个函数,方便调用 ## 二、扩展中国剩余定理 $x\equiv c_i(mod\ p_i)$的通解?这不是CRT吗? 然而我们立即会发现,本题中$p_i$不一定是互质的。 有没有其他的办法绕过互质这个条件呢。 考虑一个合并操作,如果对于任意两个式子 $$ x\equiv c_1(mod\ p_1),x\equiv c_2(mod\ p_2) $$ 我们都可以将其合并为$x\equiv c(mod\ p)$的新形式,那么合并到最后, 最后一个同余方程的解集就应该是全局的解集了。 事实上,我们只要对两个合并的式子做类似crt的操作我们就能合并出新式子。 将上面的同余方程转换为一般形式: $$ x = c_1+p_1k_1,x = c_2+p_2k_2 $$ $$ c_1+p_1k_1 = c_2+p_2k_2\to p_1k_1-p_2k_2 = c_2-c_1 $$ 联立两式,我们希望求出$x$的一个解,所以只需要找到任意一个合法的$k_1$即可,这样就能往回带算出一个合法的$x$了,这里可以调用$exgcd$。 但是有没有更优美的写法呢? 注意到我们之前实现了$ax\equiv c(mod\ p) \to x\equiv c_i(mod\ p_i)$ 事实上 $$ p_1k_1-p_2k_2 = c_2-c_1\leftrightarrow p_1k_1\equiv c_2-c_1(mod\ p_2) $$ 我们调用刚才那个函数就能解出$k_1$了!同时我们找到了$x$的一个解$x_0$。 这一个解有什么用呢?类似crt的,我们发现解集其实就是$x_0\pm lcm(p1,p2)$ , 这样每一次加的是$p1,p2$的最小公倍数,对在$(mod p1),(mod p2)$意义下的值都没有影响。 于是我们合并出了新方程:$x\equiv x_0(mod\ lcm(p1,p2))$。 所以题目给出了所有数的$lcm$不大于$10^{12}$的条件。 这样我们求出最后合并出的方程的解集,并找到满足$atk_ix \geq hp_i$的条件的最小解$x$就是答案了。 可以看出扩展中国剩余定理是中国剩余定理理想的替代品,降低了代码难度,封装性更高。 ## 三、一些细节 本题$10^{12}$,可能乘爆$long\ long$,需要快速乘。 任何时候,只要$ax\equiv c(mod\ p) \to x\equiv c_i(mod\ p_i)$的函数返回无解,那么整个局面都无解。 建议的扩展中国剩余定理写法: 龟速乘: ``` LL fprod(LL a, LL b, LL p) { LL ans = 0; while(b) { if(b & 1) ans = (ans + a) % p; a = (a + a) % p, b >>= 1; } return ans; } ``` 实现$ax\equiv c(mod\ p) \to x\equiv res(mod\ mod)$转换函数: ``` int GetEqu(LL a, LL c, LL p, LL & mod, LL & res) { LL d = gcd(a, p), x, y; if(c % d) return -1; c = (c % p + p) % p; exgcd(a, p, x, y), mod = p / d; res = fprod(x, c / d, mod); res += mod, res %= mod; return 1; } ``` 实现合并的函数: ``` int merge(LL & nr, LL & np, LL r1, LL p1) { LL r = nr, p = np, c = r1 - r; LL d = gcd(p, p1), k, mod; if(GetEqu(p, c, p1, mod, k) == -1) return -1; k = (k % mod + mod) % mod; np = p / d * p1; nr = fprod(p, k, np) + r; return 1; } ``` 总的起来,代码: ``` #include<cstdio> #include<algorithm> #include<set> #include<map> #define LL long long using namespace std; const int maxn = 1e5 + 5; int n, m; multiset<LL > st; multiset<LL >::iterator it; LL a[maxn], b[maxn], hp[maxn], p[maxn], atk[maxn]; LL res, mods, tmp, t2, mn, FinA, FinB; LL exgcd(LL a, LL b, LL &x, LL &y) { return b ? (exgcd(b, a % b, y, x), (y -= (a / b) * x)) : (x = 1, y = 0); } LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } LL fprod(LL a, LL b, LL p) { LL ans = 0; while(b) { if(b & 1) ans = (ans + a) % p; a = (a + a) % p, b >>= 1; } return ans; } int GetEqu(LL a, LL c, LL p, LL & mod, LL & res) { LL d = gcd(a, p), x, y; if(c % d) return -1; c = (c % p + p) % p; exgcd(a, p, x, y), mod = p / d; res = fprod(x, c / d, mod); res += mod, res %= mod; return 1; } int merge(LL & nr, LL & np, LL r1, LL p1) { LL r = nr, p = np, c = r1 - r; LL d = gcd(p, p1), k, mod; if(GetEqu(p, c, p1, mod, k) == -1) return -1; k = (k % mod + mod) % mod; LL l = p / d * p1; nr = fprod(p, k, l) + r; np = l; return 1; } void solve() { scanf("%d%d", &n, &m), mn = 0; for(register int i = 1; i <= n; ++i) scanf("%lld", &hp[i]); for(register int i = 1; i <= n; ++i) scanf("%lld", &p[i]); for(register int i = 1; i <= n; ++i) scanf("%lld", &a[i]); st.clear(); for(register int i = 1; i <= m; ++i) scanf("%lld", &tmp), st.insert(tmp); for(register int i = 1; i <= n; ++i) { it = st.begin(); if ((tmp = (*it)) > hp[i]) st.erase(it), atk[i] = tmp; else it = st.upper_bound(hp[i]), atk[i] = (*--it), st.erase(it); st.insert(a[i]); } FinB = 0, FinA = 1; for(register int i = 1; i <= n; ++i) { mn = max(mn, (hp[i] + atk[i] - 1) / atk[i]); if(GetEqu(atk[i], hp[i], p[i], mods, res) == -1) {printf("-1\n");return ;} if(merge(FinB, FinA, res, mods) == -1) {printf("-1\n");return;} } if(FinB < mn) FinB += ((mn - FinB - 1) / FinA + 1) * FinA; printf("%lld\n", FinB); } int main() { int t; scanf("%d", &t); while(t--) solve(); return 0; } ``` ~~有了excrt妈妈再也不用担心我crt写跪了~~
上一篇:
CF Educational Codeforces Round 49 E. Inverse Coloring
下一篇:
CF#483 Div2 D. XOR-pyramid
0
赞
444 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册