本文主要是介绍csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉这也是自己独自做扩展欧几里得算法的题目
题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解
下面介绍一下exgcd的一些知识点：求ax + by = c的解
一、首先求ax + by = gcd(a,b)的解 这个只要用exgcd的模板就可以求出来，设求得的解为x0,y0，
那么其他解为x = x0 + b/gcd(a,b)*t; y = y0 - a/gcd(a,b);(t为任意整数)
二、如果c % gcd(a,b) 不为0，那么ax + by = c无解；否则ax + by = c的解表示为x1 = x0*c/(gcd(a,b)),y1 = y0*c/gcd(a,b)
那么其他解为x = x1 + b/gcd(a,b); y = y1 - a/gcd(a,b);
如果了解了这些知识点，那么就可以解这个题目了
代码如下（附注释）：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define ll long long
#define inf 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;void gcd(ll a, ll b, ll &d, ll &x, ll&y)//扩展欧几里得的模板
{if(!b){d = a; x = 1; y = 0; } else{gcd(b, a%b, d, y, x);y -= x*(a/b); }}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);ios::sync_with_stdio(false);int t;cin>>t;while(t--){ll n1,n2,f1,f2,d1,d2;ll d, x, y, temp;cin>>n1>>f1>>d1>>n2>>f2>>d2;//求d1*x - d2*y = f2- f1 ;// x属于0---n1-1,y属于0---n2-1 gcd(d1, -d2, d, x, y); ll c = f2 - f1;if(c % d){cout<<"0\n"<<endl;continue; } ll x1, y1;x1 = x*(c/d);//d1*x - d2*y = f2- f1 的一组解 y1 = y*(c/d);// cout<<x1<<" "<<y1<<endl; ll k1, k2;k1 = d2/abs(d);//y = kx + b中的k ,k > 0 k2 = d1/abs(d);if(x1 < 0 || y1 < 0)//求最小整数解 {int i = 1; while(1){if(x1 + k1*i >=0 && y1 + k2*i >=0)break; i++; } x1 = x1 + k1*i;y1 = y1 + k2*i;}else{int i = 1;while(1){if(x1 - k1*i < 0 || y1 - k2*i < 0)break;i++; } x1 = x1 - k1*(i-1);y1 = y1 - k2*(i-1);}//最小整数解为x1,y1 // cout<<x1<<" "<<y1<<endl; if(x1 > n1-1 || y1 > n2 -1){cout<<0<<endl; continue; }//ll t1,t2;t1 = (n1 - 1 - x1)/k1;//求的在[0,n1-1]区间内的解的个数t2 = (n2 - 1 - y1)/k2;//求的在[0,n2-1]区间内的解的个数 cout<<min(t1,t2)+1<<endl;}// P; return 0;
}
这篇关于csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
