加载中...

解一元二次不定方程

发表于2023-08-19|OI（高中）2023-2024赛季

|总字数:263|阅读时长:1分钟|浏览量:

解一元二次不定方程

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132385405

https://www.luogu.com.cn/problem/P5656

求解：

在这里插入图片描述

有解充要条件：令 $d=\gcd(a,b),c\bmod d=0$
exgcd，背吧

int exgcd(int a, int b, int &x, int &y) {
	int d=a; 
	if(b==0) x=1, y=0; 
	else {
		d=exgcd(b, a%b, y, x); 
		y-=a/b*x; 
	}
	return d; 
}

合法解：令 $t=c/d$ ，使 $x=x\times t,y=y\times t$
任意解：令 $p=b/d,q=a/d$ ，则 $x=x+kp,y=y-kq$

然后剩下就是奇怪判断了

在这里插入图片描述

例题：ABC315G

https://atcoder.jp/contests/abc315/tasks/abc315_g

给 $x,y$ 的范围变成 $[1,n]$

在这里插入图片描述

写的时候都不想看，反正到时候多手推，多判断，多拍拍即可

多对拍，个人感觉挺好拍的

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/90b99e5f

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

相关推荐

【NOIP2021 方差】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1∑i=1n(ai−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1∑i=1nai。我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...

【[AGC005B] Minimum Sum】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633178.html 题目链接从1开始从小到大考虑，用set维护每个数左右的扩散范围，然后答案为这个数的区间就是左端点个数 ×\times× 右端点个数。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859// Problem: AT2060 [AGC005B] M...

矩阵树定理

矩阵树定理本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132152078 启蒙： http://zhengruioi.com/contest/1416 T1，T2的10分暴力（后面是论文科技，不搞了） https://www.luogu.com.cn/problem/P6178 O(n3)O(n^3)O(n3) 解决无向图生成树计数问题。行列式交换两行，行列式变号一行整体加上 kkk 倍另一行，行列式符号不变行列式如果只有其中对角线非...

【P1270 “访问”美术馆】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接典型的树形dp。设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=max⁡y∈xmax⁡i=0smax⁡j=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...

【CF580C Kefa and Park】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16195913.html 题目链接题目 Kefa decided to celebrate his first big salary by going to the restaurant. He lives by an unusual park. The park is a rooted tree consisting of $ n $ vertices with the root at vertex $ 1 $ . Vertex $ 1 $ ...

质数与数差类题目：ZR2639三色堇

质数与数差类题目：ZR2639三色堇本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132325425 Trick 1 题目要求维护差的平方和。但发现差得数量很少。对于维护和差有关的东西（比如此题中的 ∑(ai−ai−1)2\sum(a_i-a_{i-1})^2∑(ai−ai−1)2 ），如果差的数量很少，可以直接维护差的数量 fif_ifi ，最后可以计算为 i2×fii^2\times f_ii2×fi Trick 2 考虑数之间的差怎么转...

数据加载中