exgcd 模板没有 exgcd 标签吗?
查看原帖
exgcd 模板没有 exgcd 标签吗?
764746
Sweet_Wrapping_Grass楼主2023/11/2 13:12

rt,建议补充。

由于历史原因,tag242 原来是 扩欧(并没有区分是 扩展欧几里得算法 还是 扩展欧拉定理),导致有一部分与 exgcd 和 exEuler 相关的题目都被打上了这个标签。根据每道题目的解法与原来 tag242 的关联点,我在这里对含有 tag242 的题目进行了整理(并没有 AC 所有题目,根据题解判断的,有错轻喷)。既然洛谷现在把 tag242 确定为 exgcd,我建议:

  • 对于关联点为 二元一次不定方程 或 线性同余方程 的,保留 exgcd 标签;
  • 对于关联点为 求逆元 的,由于逆元不一定需要使用 exgcd,可以删掉 exgcd 标签,补充 逆元 标签;
  • 对于关联点为 扩展欧拉定理 的,新建算法标签 扩展欧拉定理,exEuler,删掉 exgcd 标签并补充 exEuler 标签;
  • 对于其他题目,不太清楚如何处理,管理员看着办?
2023/11/2 13:12
加载中...