首页 > 牛牛的方程式
开通博客写题解
头像 Deep_Dark_FAntasy♂
发表于 2020-10-20 11:35:06
ax+by=c有解结论的推广gcd(a,b)|c别忘了特判a=b=0的时候，c=0，c/=0情况代码： #include<bits/stdc++.h> using namespace std; #define int long long signed main() { int t 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Isshiki_Hugh
发表于 2020-10-17 22:19:05
T2牛牛的猜球游戏 题面 更好的阅读体验 记忆化+映射做的。 思路应该挺显然的，就是记忆化一下连续操作后的结果。 比如操作为： 1 2 2 3的时候，我们可以直接记录两次操作后的数组为 1 2 0 3 4 5 6 7 8 9也就是可以直接存一下第 次操作以后 ~ 序列的结果，空间是 ，看起来 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Indra
发表于 2020-10-17 22:24:57
T2 通过莫队实现。从末端加入一次操作，等价于交换当前第a个和第b个（位置）的杯子，撤销则等同于交换回来。从首端加入一次操作，等价于从一开始就将第a个和第b个（编号）的球交换，撤销则等同于交换回来。所以就在过程中存下每个球的位置和每个位置上的球。见代码：https://ac.nowcoder.com 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 --嘤色暴撃--
发表于 2020-10-17 23:25:52
每次重新换球改变的是杯子与杯子间的相对位置因此对于杯子的排列如0 1 2 3 4 5 6 7 8 9为初始状态调换第3个和第4个相对来说顺序变为 =( 0 1 2 4 3 5 6 7 8 9 )以这种串的形式表示原来的第个纸杯移动到了的位置即对于目前第三个杯子和第四个杯子换了状态可叠加即( 0 1 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 xxoy
发表于 2020-10-17 22:22:38
题目详解：扩展欧几里得算法的应用。ax+by=gcd(a,b)。用朴素的语言讲就是两个数a,b。对于整数x，y：ax+by可以组成 a，b最大公约数的任意倍数。打个比方 2和7。2x+7y可以组成任意整数。1=2（-3）+72=2+03=2（-2）+7……3和15则只能组成3的倍数。 所以对于两个数 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Isshiki_Hugh
发表于 2020-10-19 12:56:05
T3牛牛的凑数游戏 题面 更好的阅读体验 代码参考了Deep_Kevin神的 做的时候还在想，这东西我似乎连暴力都不会，想想如果要枚举区间内所有可能出现的和那不是光枚举就得 了，无力 ( 赛后：我是***。 首先，我们必须解决如何在多项式时间内找到这个数的问题，其他的再说。 为了让数据更好处理我 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ZigZagKmp
发表于 2020-10-18 23:23:48
本场全部题解见此 更好的阅读体验 A 牛牛的方程式 题意简述 给定 ，询问是否存在一组整数解 ，满足 。 多测， 。 算法标签 数论 同余 算法分析 如果只有两项，即 这种形式，可以直接套用裴蜀定理，该方程有整数解等价于 。 由上面的式子，我们不难发现， 可以表示所有整除 的数。 那 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zrzring
发表于 2020-10-19 17:19:45
更好的阅读体验 裴蜀定理的推广，若，则，负数可以转化为正数处理 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorit 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 tuscjaf
发表于 2020-10-18 11:21:54
题目链接 思路 这道题我们要求 是否有整数解 ，我们可以先讨论 是否有整数解，然后再看 ，是否有整数解，于是我们可以考虑用裴蜀定理 裴蜀定理 设 ，则存在整数 使得 所以存在整数 使得 的条件是 接下来我们求出 的最大公约数即可，根据题目还有 ，以此类推，我们只需要判断是否 且 综 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”