关键词：
<更新提示>
<第一次更新>
<正文>
扩展欧几里得算法
顾名思义，扩欧就是扩展欧几里得算法，那么我们先来简单地回顾一下这个经典数论算法。
对于形如(ax+by=c)的不定方程，扩展欧几里得算法可以在(O(5log_10mina,b))的时间内找到该方程的一组特解，或辅助(gcd)判断该方程无解。
对于扩欧的详细讲解，可见『扩展欧几里得算法 Extended Euclid』。
那么我们注意到一个问题，扩展欧几里得算法求的只是一组特解。事实上，我们可以根据如下公式得到不定方程的通解:
[
egincases
x=x_0+kfracbgcd(a,b)
\\y=y_0+kfracagcd(a,b)
endcases
]
其中，(x_0,y_0)是方程的一组特解，(kin Z)。
关于正确性，其实代入就能发现多余项可以直接抵消，与此同时，我们发现与(a,b)分别相乘的额外项构成了(lcm(a,b))，这就能保证所有解都能由这个式子表示。
实际运用的时候，我们通常这样得到最小正整数解:(x=(x_0\\%fracbgcd(a,b)+fracbgcd(a,b))\\%fracbgcd(a,b))。
青蛙的约会
Description
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝着对方那里跳，直到碰面为止。
可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input Format
一行5个整数x，y，m，n，L，其中x≠y，m、n≠0，L>0。m，n的符号表示了相应的青蛙的前进方向。
Output Format
在单独一行里输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行“Impossible”。
Sample Input
1 2 3 4 5 Sample Output
4解析
这是一道比较模板的题。我们设两只青蛙走了(t)步，它们追了(k)圈，那么就可以得到
[
x+mt=y+nt+kl
\\?(n-m)t+kl=x-y
]
那么这就是扩欧方程的形式了，直接利用扩展欧几里得求出一个解(t_0)，然后利用上述通解公式得到最小整数解即可。
(Code:)
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define mset(name,val) memset(name,val,sizeof name)
#define mcopy(to,from) memcpy(to,from,sizeof from)
#define filein(str) freopen(str".in","r",stdin)
#define fileout(str) freopen(str".out","w",stdout)
inline long long Exeuclid(long long a,long long &x,long long b,long long &y,long long c)
if (b==0)x=c/a,y=0;return a;
else
long long p=Exeuclid(b,x,a%b,y,c);
long long x_=x,y_=y;
x=y_ , y=x_-a/b*y_;
return p;
inline long long gcd(long long a,long long b)
return b ? gcd(b,a%b) : a ;
long long x,y,n,m,l,x_,y_;
inline void input(void)
scanf("%lld%lld%lld%lld%lld",&x,&y,&n,&m,&l);
inline long long solve(void)
long long d=gcd(m-n,l);
if ( (x-y) % d )return -1;
Exeuclid(m-n,x_,l,y_,x-y);
long long res = ( x_ % (l/d) + (l/d) ) % (l/d);
return res;
int main(void)
input();
long long ans=solve();
if (ans==-1)printf("Impossible
");
else printf("%lld
",ans);
return 0;
<后记>
java静态代码块的简单运用(代码片段)
packageCode504;/*静态代码块的格式：publicclass类名称static//静态代码块的内容特点：当第一次使用本类时，静态代码块执行唯一的一次。*/publicclassCodeStaticpublicstaticvoidmain(String[]args)CodePersonone=newCodePerson();CodePersontwo 查看详情
opencv简单卷积运用(代码片段)
importcv2ascvimportnumpyasnpimg=cv.imread(‘learn.jpg‘,cv.IMREAD_GRAYSCALE)cv.imshow(‘firstimage‘,img)img_size=img.shapeprint(img_size)imgkernel=np.array([[-2,-1,0],[-1,1,1],[0,1,2]])print(imgkernel)#利 查看详情
pythonrequests的安装与简单运用(代码片段)
...llib2提供了大部分需要的HTTP功能，但是API太逆天了，一个简单的功能就需要一大堆代码。我也看了下requests的文档，确实很简单，适合我这种懒人。下面就是一些简单指南。1.安装安装很简单， 查看详情
mybatis框架的简单运用(代码片段)
一、配置流程1.流程示意图（通过XML映射文件实现）：2.流程：2.1导入包：2.1.1下载包 数据库驱动包（本文以MySQL为例）：https://mvnrepository.com/artifact/mysql/mysql-connector-java Mybatis框架包：https://mvnrepository.com/artifact/org.mybatis/myb... 查看详情
httpclient的简单运用(代码片段)
...研究决定使用HttpClient，自己封装了一个HttpClient工具类，简单轻松的实现get，post，put和delete请求，希望分享给大家。1.什么是HttpClient HTTP协议可能是现在Internet上使用得最多、最重要的协议了，越来越多的Java应用程序需要直... 查看详情
quartz初识以及简单运用(代码片段)
...tz是一个完全由Java编写的一个开源的任务调度框架，说的简单点就是开发人员可以通过Quartz根据时间间隔调度任务，例如：每隔一小时命令程序执行一个任务每个月命令程序执行一个任务指定某月末日命令程序执行一个任务……... 查看详情
数论基础题费马引理+卡特兰数+lucas定理+同余方程+扩欧(代码片段)
1119机器人走方格V2费马引理+组合数预处理的解法一错了，但复杂度是对的，不知道为啥卡了#include<iostream>#defineintlonglong#defineendl'\\n'usingnamespacestd;constintinf=1e18;constintN=1e6+5;constint 查看详情
docker简单运用(代码片段)
Docker帮助系统管理员和程序员在容器中开发应用程序，并且可以扩展到成千上万的节点，容器和VM（虚拟机）的主要区别是，容器提供了基于进程的隔离，而虚拟机提供了资源的完全隔离。虚拟机可能需要一分钟来启动，而容器... 查看详情
npm简单运用(代码片段)
npm是nodejs附带的包管理工具，他的主要作用有三种1.从服务器下载别人的包使用；2.从服务器下载别人的命令行工具使用；3.自己发布包或者命令行工具到服务器。可以使用npm-v的方法来查看npm的版本号npm-v//5.6.0如果查询失败，可... 查看详情
.net运用entityfromwork搭建的一个简单发帖功能案例(代码片段)
数据库设计创建数据库：ChangeDB：Catelog类型表，Article文章表数据表Catelog类型表字段名类型说明idint类型IDNamenvarchar(50)类型名称Commentnvarchar(50)类型说明Article文章表字段名类型说明idint编号Titlenvarchar(50)标题Authornvarchar(50... 查看详情
最简单的多线程并发与守护线程与join的运用(代码片段)
importthreadingimporttimedefrun(n):print("talk",n)time.sleep(3)#run("t1")#run("t2")t1=threading.Thread(target=run,args=("t1",))t2=threading.Thread(target=run,args=("t2",))#t1.start()#t2.start()##类的多线程 查看详情
cf633a(代码片段)
...10000其实就是求ax+by=c能否求出a,b都为自然数的一组解，用扩欧求出来任意一组，然后运用公式(x+k*b/gcd(a,b),y-k*a/gcd(a,b)),k取任意整数判断 #include<iostream>usingnamespacestd;voidGcd(inta,intb,int&d,i 查看详情
拓扑结构+差分约束+slf最长路+扩欧(代码片段)
倦怠，但还不能休息，我的牌还没有到手~E.ExchangingGifts997m过了，超时了就多交几次就可能过吧……可以把vector改成链式前向行，vector改为二维数组，会优化100ms左右。#include<bits/stdc++.h>#defineendl'\\n... 查看详情
几何运用题(代码片段)
1037.有效的回旋镖参考题解：【宫水三叶】简单计算几何运用题一共三个点，分别使用两个点计算向量，随后判断向量叉积是否为0。classSolutionpublicbooleanisBoomerang(int[][]points)int[]v1=points[1][0]-points[0][0],points[1][1]-points[0... 查看详情
同余方程(扩欧模板)(代码片段)
洛咕题意:求关于x的同余方程(axequiv1pmodb)的最小正整数解.方程(axequiv1pmodb)有解当且仅当(gcd(a,b)=1).所以方程可写为(a*x+b*y=1),用扩展欧几里得算法求出一组特解(x_0,y_0),通解是所有模b与(x_0)同余的整数,题目要求最小的解,故答案就是((... 查看详情
简单运用理解webpack(代码片段)
流程图：一定义：js模块打包器 把所有的依赖文件生成一个图，打包成文件如何安装：npminit-y初始化项目 npmiwebpack-cil-D安装配置文件：在创建的文件夹根目录创建一个 webpack.config.js ... 查看详情
资深程序员带你完全熟练掌握requests以及它的安装与简单运用！(代码片段)
是不是很简单？比urllib2和urllib简单直观的多？！那请接着看快速指南吧。3.快速指南3.1发送请求发送请求很简单的，首先要导入requests模块：前两个例子很正常，能正常打开的返回200，不能正常打开的返回404。但第三个就有点奇... 查看详情
工作中标准库容器的运用（游戏编程需求）(代码片段)
C++标准库的容器分为序列容器和关联容器。序列容器简单的有vector，list，deque，复杂的还有配接器stack，queue，priority_queue。关联容器简单的有set，map，复杂的有multiset，multimap，这都是基于RB-tree的，基于hashtable的也有hash-set，hash-... 查看详情