【Exgcd】斩杀线计算大师

【题目链接】传送门

【题意】

　　给定a,b,c,k，必定存在ax+by+cz=k，请求出x,y,z

【题解-解法1】

　　因为必定有解，所以枚举c的倍数，然后对 ax + by = k-c*i进行exgcd。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 typedef long long ll ;
 8 const ll mod = 1e9 + 7 ;
 9 const int N = 1e3 + 10;
10 
11 ll exgcd( ll a , ll b , ll &x , ll &y ){
12     if( b == 0 ){
13         x = 1 , y = 0 ;
14         return a ;
15     }
16 
17     ll r = exgcd( b , a % b , y , x );
18     y = y - a/b * x ;
19     return r ;
20 
21 }
22 int main()
23 {
24     ll a , b , c , k ;
25     ll x , y , z ;
26     scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
27     
28     ll Gcd = exgcd( a , b , x , y );
29 
30     for( int i = 0 ; i < k / c ; i ++ ){
31         if( (k - i * c) % Gcd == 0 ){
32             ll tmp = (k - i * c) ;
33             exgcd( a , b , x , y );        
34             //扩大 ( k - i * c ) / gcd 倍
35             x = x * tmp / Gcd ;
36             y = y * tmp / Gcd ;
37             
38             //计算最小正整数
39             x = (x % (b / Gcd) + (b / Gcd)) % (b / Gcd);
40             y = (tmp - x * a) / b ;
41             z = i ;
42             if( x >= 0 && y >= 0 )
43                 break;
44 
45         }
46     }
47     printf("%lld %lld %lld
",x,y,z);
48     return 0;
49 }

View Code

【题解-解法2】

　　同余最短路