ax在c语言中意思啊,【数论】整理关于ax+by=c

浅浅的花香味﹌ 2022-10-15 00:55 193阅读 0赞

整理关于 \\(\\rm\{ax+by=c\}\\)，遇到的一系列

在这里，\\(x\\) ，\\(y\\) 是变量，\\(a,\\;b,\\;c\\) 是常量

前置：

对于二元一次不定方程 \\(ax+by=c\\)，有整数解的充要条件是 \\((a,b)|c\\) ；

设 \\(a=\\frac a\{gcd(a,b)\}\\), \\(b=\\frac b\{gcd(a,b)\}\\)，\\(c=\\frac c\{gcd(a,b)\}\\)，则此时 \\(gcd(a,b)=1\\)；

若 \\(gcd(a,b)=1\\)，且不定方程 \\(ax+by=c\\) 有整数解 \\(x=x\_0,\\,y=y\_0\\) ，则它的一切整数解可表示成：

\\\[x=x\_0+bt\\\\y=y\_0-at\\;(t\\in \\rm Z)

\\\]

exgcd可求得 \\(ax+by=gcd(a,b)\\)的特解，\\(x\_0,\\,y\_0\\)

所以 \\(ax+by=c\\)的特解可表示成 :

\\\[x\_0=x\_0\\cdot\\frac\{c\}\{gcd(a,b)\}=x\_0\\cdot c\\\\

y\_0=y\_0\\cdot\\frac\{c\}\{gcd(a,b)\}=y\_0\\cdot c

\\\]

由 \\(\\rm 3\\)可得 \\(ax+by=c\\) 的通解 \\(x,\\,y\\)

设以下， \\(ax+by=c\\) 中，均是 \\(gcd(a,b)=1\\)。

1,求 \\(\\rm\{ax+by=c\}\\), \\(x\\)的最小正整数解

设 \\(x\_1\\) 为 \\(x\\) 的最小正整数解，则 \\(x\_1\\) :

\\\[x\_1=(x\\%b+b)\\%b\\\\

对应\\;\\;y\_1=\\frac\{c-a\*x\_1\}b

\\\]

2, 求 \\(\\rm\{ax+by\}\\) 的最大不可解 \\(\\rm c\\)，且满足 \\(\\rm\{x>0,y>0\}\\) : \\(\\rm\{c=a\\times b\}\\)

3, 求 \\(\\rm\{ax+by\}\\) 的最大不可解 \\(\\rm c\\) , 且满足 \\(\\rm\{x\\geq0,y\\geq0\}\\) : \\(\\rm\{c=a\\times b-a-b\}\\)

4,求 \\(\\rm\{ax+by+cz=k\}\\) 的任意一组解，且满足 \\(\\rm\{x\\geq0,y\\geq0,z\\geq0\}\\) :

其中：\\(1\\leq a,b,c\\leq10^5 ,0\\leq k\\leq 10^\{12\}\\) ，保证数据有解

\\(ax+by=k-cz\\) 有解的前提是 \\(gcd(a,b)|(k-cz)\\)，则需枚举z使得满足条件\\(gcd(a,b)|(k-cz)\\)下，可解的符合的 \\(x,\\,y\\)。

设 \\(g=gcd(a,b)\\) \\(ec=k\\%g\\)，则所求的 \\(z\\) 需满足\\(zc-tg=ec\\)，且 \\(z\\geq0\\)。

所以求出最小 \\(z\\)，再枚举满足通项公式的 \\(z\\)，直到有解。

\#include

typedef long long ll;

using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=2e5+5;

ll exgcd(ll a,ll b,ll &x,ll &y)

\{

if(!b)\{

x=1;y=0;

return a;

\}

ll g=exgcd(b,a%b,x,y);

ll t=x;

x=y;

y=t-a/b\*y;

return g;

\}

void solve(ll a,ll&b,ll c,ll&x,ll&y)

\{

ll g=\_\_gcd(a,b),x0,y0;

a/=g;b/=g;c/=g;

exgcd(a,b,x0,y0);

x0\*=c;y0\*=c;

x=x0+b;//y=y0-a;

x=(x%abs(b)+abs(b))%abs(b);y=(c-a\*x)/b;

\}

int main()

\{

ll a,b,c,k,g,ec,x,y,z,t,tb,tk,ttb;

scanf("%lld%lld%lld%lld",&a,&b,&c,&k);

g=\_\_gcd(a,b);

ec=k%g;

tb=-g;

solve(c,tb,ec,z,t);

tb=abs(tb);

do\{

tk=k-z\*c;ttb=b;

solve(a,ttb,tk,x,y);

if(x>=0&&y>=0)

\{

printf("%lld %lld %lld\\n",x,y,z);

break;

\}

z+=tb;

\}while(1);

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关 c语言中％d是什么意思

"%d" 是 c 语言中格式化字符串的一部分，表示将后面的整数数据以十进制的形式输出。它是一种格式控制字符，用于指示 printf 和 scanf 函数如何格式化和读取数据。例

╰+哭是因爲堅強的太久メ/ 2024年03月25日 19:00/ 0 赞/ 96 阅读

相关 join是什么意思啊(join是什么意思啊)

join和join in有什么区别么？怎样使用他们？请详细说明，谢谢 join和join in的区别为：意思不同、用法不同、侧重点不同。一、意思不同 1、join：

布满荆棘的人生/ 2023年09月26日 14:56/ 0 赞/ 38 阅读

相关 char在c语言中的意思(char在c++中的意思)

在编程中char是什么意思在编程中char是申明一个字符型变量的语句。比如 char str; 这样申明后，str就表示是一个长度为一个字节的字符变量。在C语言中一

旧城等待，/ 2023年09月26日 14:04/ 0 赞/ 95 阅读

相关 c语言关键字及其含义(1在c语言中是什么意思)

C语言的关键字有几个。。。else选择结构int基本整型数据long长整型数据registerCPU内部寄存的变量return用于返回函数的返回值short短整型数据s

布满荆棘的人生/ 2023年09月26日 12:47/ 0 赞/ 170 阅读

相关 depth是什么意思啊(depth是什么意思啊英语)

in the depth of的depth加不加s有什么区别？ in the depth of\_百度翻译 in the depth of 英\[in ðə depθ

迷南。/ 2023年09月26日 12:12/ 0 赞/ 96 阅读

相关 ::在c++中的意思

“::”在c++中一. 作用域符号 “：：”前面是类名称，后面一般是该类的成员名称例类A中包含member1 A::member1 二.全局作用域符号用于区分全局

朱雀/ 2022年12月20日 11:29/ 0 赞/ 249 阅读

相关 C语言中 -＞是什么意思？

\-> 是一个整体，它是用于指向结构体、C++中的class等含有子数据的指针用来取子数据。换种说法，如果我们在C语言中定义了一个结构体，然后申明一个指针指向这个结构体，那么我

系统管理员/ 2022年12月01日 01:24/ 0 赞/ 471 阅读

相关在c语言中 n的作用是什么,c语言中(n)的意思，C语言中‘\n'是什么意思

C语言中‘\\n'是什么意思 \\n' 的意思是：回2113车换行。将当前位置移到下一行的5261开头。 1、\\n是换行符，4102通常在输出中用作格式控制；1653\\

小灰灰/ 2022年10月20日 13:53/ 0 赞/ 398 阅读

相关 ax在c语言中意思啊,【数论】整理关于ax+by=c

整理关于 \\(\\rm\{ax+by=c\}\\)，遇到的一系列在这里，\\(x\\) ，\\(y\\) 是变量，\\(a,\\;b,\\;c\\) 是常量前置：

浅浅的花香味﹌/ 2022年10月15日 00:55/ 0 赞/ 194 阅读

相关 C语言贪心导弹拦不住啊啊啊啊

最少拦截系统 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem D

落日映苍穹つ/ 2022年06月01日 08:16/ 0 赞/ 265 阅读