csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

2024-09-09 17:38

本文主要是介绍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 (扩展欧几里得算法的简单应用)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1151834

相关文章

5分钟获取deepseek api并搭建简易问答应用

《5分钟获取deepseekapi并搭建简易问答应用》本文主要介绍了5分钟获取deepseekapi并搭建简易问答应用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需... 目录1、获取api2、获取base_url和chat_model3、配置模型参数方法一:终端中临时将加

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为

Python调用另一个py文件并传递参数常见的方法及其应用场景

《Python调用另一个py文件并传递参数常见的方法及其应用场景》:本文主要介绍在Python中调用另一个py文件并传递参数的几种常见方法,包括使用import语句、exec函数、subproce... 目录前言1. 使用import语句1.1 基本用法1.2 导入特定函数1.3 处理文件路径2. 使用ex

利用Python编写一个简单的聊天机器人

《利用Python编写一个简单的聊天机器人》这篇文章主要为大家详细介绍了如何利用Python编写一个简单的聊天机器人,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 使用 python 编写一个简单的聊天机器人可以从最基础的逻辑开始,然后逐步加入更复杂的功能。这里我们将先实现一个简单的

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

将Python应用部署到生产环境的小技巧分享

《将Python应用部署到生产环境的小技巧分享》文章主要讲述了在将Python应用程序部署到生产环境之前,需要进行的准备工作和最佳实践,包括心态调整、代码审查、测试覆盖率提升、配置文件优化、日志记录完... 目录部署前夜:从开发到生产的心理准备与检查清单环境搭建:打造稳固的应用运行平台自动化流水线:让部署像

使用IntelliJ IDEA创建简单的Java Web项目完整步骤

《使用IntelliJIDEA创建简单的JavaWeb项目完整步骤》:本文主要介绍如何使用IntelliJIDEA创建一个简单的JavaWeb项目,实现登录、注册和查看用户列表功能,使用Se... 目录前置准备项目功能实现步骤1. 创建项目2. 配置 Tomcat3. 项目文件结构4. 创建数据库和表5.

使用PyQt5编写一个简单的取色器

《使用PyQt5编写一个简单的取色器》:本文主要介绍PyQt5搭建的一个取色器,一共写了两款应用,一款使用快捷键捕获鼠标附近图像的RGB和16进制颜色编码,一款跟随鼠标刷新图像的RGB和16... 目录取色器1取色器2PyQt5搭建的一个取色器,一共写了两款应用,一款使用快捷键捕获鼠标附近图像的RGB和16

四种简单方法 轻松进入电脑主板 BIOS 或 UEFI 固件设置

《四种简单方法轻松进入电脑主板BIOS或UEFI固件设置》设置BIOS/UEFI是计算机维护和管理中的一项重要任务,它允许用户配置计算机的启动选项、硬件设置和其他关键参数,该怎么进入呢?下面... 随着计算机技术的发展,大多数主流 PC 和笔记本已经从传统 BIOS 转向了 UEFI 固件。很多时候,我们也

Linux中Curl参数详解实践应用

《Linux中Curl参数详解实践应用》在现代网络开发和运维工作中,curl命令是一个不可或缺的工具,它是一个利用URL语法在命令行下工作的文件传输工具,支持多种协议,如HTTP、HTTPS、FTP等... 目录引言一、基础请求参数1. -X 或 --request2. -d 或 --data3. -H 或