标签 - 扩展欧几里得

? 解题记录 ? ? UOJ ? ? 中国剩余定理 ? ? 扩展欧几里得 ?    2018-09-16 09:39:49    432    0    0
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$求解
? 解题记录 ? ? Codeforces ? ? 扩展欧几里得 ?    2018-07-05 23:00:10    649    0    0
time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Consider a billiard table of rectangular size n×m" data-mce-tabindex="0">n×mn×m with four pockets. Let's introduce a coordinate system with the origin at th
? 解题记录 ? ? 洛谷 ? ? 扩展欧几里得 ? ? 模板 ?    2017-08-21 17:17:21    522    0    0
题目背景这是一道模板题 题目描述给定n,p求1~n中所有整数在模p意义下的乘法逆元。 输入输出格式输入格式:   一行n,p   输出格式:   n行,第i行表示i在模p意义下的逆元。   输入输出样例输入样例#1:10 13 输出样例#1:1 7 9 10 8 11 2 5 3 4 说明1 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×10​6​​,n<p<20000528 输入保证 pp 为质数。 突然觉得之前太傻了……居然拿逆元硬转成了线