简单的网站开发,网站网络拓扑图,班级网站设计论文,搜索引擎优化的缺点包括https://vjudge.net/contest/218366#problem/J 第一步追及公式要写对#xff1a;ynk-(xmk)pL (n-m)klpx-y 可以看出扩展欧几里得原型#xff0c;这里注意扩展欧几里得求出的是任意解#xff0c;非最优#xff0c;要推出最小解k。 (n-m)xlygcd (n-m)(x*(x-y)/gcd)… https://vjudge.net/contest/218366#problem/J 第一步追及公式要写对ynk-(xmk)pL (n-m)klpx-y 可以看出扩展欧几里得原型这里注意扩展欧几里得求出的是任意解非最优要推出最小解k。 (n-m)xlygcd (n-m)(x*(x-y)/gcd) l*y*(x-y)/gcd x-y 则k x*(x-y)/gcd某一解非最小由于k每次可转移t l/gcd 最小解为(k%tt)%t。 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includecstdlib6 #includecmath7 #includevector8 #includestack9 #includequeue
10 #define lson l, m, rt1
11 #define rson m1, r, rt1|1
12 #define IO ios::sync_with_stdio(false);cin.tie(0);
13 #define INF 0x3f3f3f3f
14 #define MAXN 500010
15 const int MOD1e97;
16 typedef long long ll;
17 using namespace std;
18 ll ext_gcd(ll a, ll b, ll x, ll y)
19 {
20 if(b 0){
21 x 1;
22 y 0;
23 return a;
24 }
25 ll r ext_gcd(b, a%b, x, y);
26 ll t x;
27 x y;
28 y t-(a/b)*y;
29 return r;
30 }
31 int main()
32 {
33 ll n, m, x, y, l, k, p;
34 cin x y m n l;
35 ll r ext_gcd(n-m, l, k, p);//k和p为任意解非最优
36 if((x-y)%r!0){
37 cout Impossible endl;
38 }
39 else{
40 ll t l/r;//k每次转移量
41 ll ans k*(x-y)/r;//从扩展欧几里得标准公式转到我们所列公式求得的k值
42 cout (ans%tt)%t endl;
43 }
44 return 0;
45 } 转载于:https://www.cnblogs.com/Surprisezang/p/8733200.html
