[1]青蛙的约会
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具***置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B ，并且规定纬度线上东经 0 度处为原点，由东往西为正方向，单位长度 1 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x ，青蛙 B 的出发点坐标是 y 。青蛙 A 一次能跳 m 米，青蛙 B 一次能跳 n 米，两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。
输入
输入只包括一行 5 个整数 x,y,m,n,L 。
对于100%的数据，0<=x,y<209, 0<m,n<209, 0<L<2.1109。保证x!=y。
输出
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行 Impossible 。
样例输入
1 2 3 4 5
样例输出
4
题目类型:
同余问题
思路:
参考陈同学, 设两只青蛙跳了 T 步，则A的坐标为X+mT，B的坐标为Y+nT。相遇的充要条件为X+mT - (Y+nT) = LP（P为整数），所以 (n - m)T+LP = x – y，L>0,
然后用exgcd求解x和y的值,如果青蛙可以碰面的话,方程两边同除gcd得到的都应该是整数,也就是(a)x-y%(ans)gcd=0,不然两只青蛙就不能碰面了
然后计算得到的x，y要c/gcd才是真正的解x1，y1(因为本来就是求解ax+by=gcd（a，b）这个方程的)
然后x，y的解集为x=x1+b/gcdt，y=y0-a/gcdt。

#include<iostream>
#include<cstdio>
#define ll long long 
using namespace std;
ll ans,x1,y1;

ll exgcd(ll a,ll b,ll &x1, ll &y1)
{
    if(!b)
    {
        x1=1;
        y1=0;
        return a;
    }
    ans=exgcd(b,a%b,x1,y1);
    ll t=x1;
    x1=y1;
    y1=t-a/b*y1;
    return ans;
}

int main()
{
    ll n,m,x,y,l;
    cin>>x>>y>>m>>n>>l;
    ll b=n-m,a=x-y;
    if(b<0)
    {
        b=-b;
        a=-a;
    }//处理负数 
    exgcd(b,l,x1,y1);
    if(a%ans!=0)//判断方程有无解。 
        cout<<"Impossible";
    else
        cout<<((x1*(a/ans))%(l/ans)+(l/ans))%(l/ans);//处理负数 
}

[2] 五指山
题目描述
大圣在佛祖的手掌中。
我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,⋯,n−1，而大圣每次飞的距离为 d。现在大圣所在的位置记为 x，而大圣想去的地方在 y。要你告诉大圣至少要飞多少次才能到达目的地。
对于全部数据，2<n<109,0<d<n,0≤x,y<n。
输入
有多组测试数据。
第一行是一个正整数 T，表示测试数据的组数；
每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 n，筋斗所能飞的距离 d，大圣的初始位置 x 和大圣想去的地方 y。
注意孙悟空的筋斗云只沿着逆时针方向翻。
输出
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。如果无论翻多少个筋斗云也不能到达，输出 Impossible。
样例输入
2
3 2 0 2
3 2 0 1
样例输出
1
2
思路:
就是套exgcd的板子求解最小正整数解,然后距离是在一个环上面算

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//求解公约数
ll gcd(ll a,ll b)
{
    while(b)
    {
        ll t=a;
        a=b;
        b=t%a;
    }
    return a;
}
ll a,b,c,d,e,T,x,y,tmp;
//计算x和y的值
void exgcd(ll a,ll b,ll&x,ll&y)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    tmp=x;
    x=y;
    y=tmp-a/b*y;
}
int main(){
    cin>>T;
    while(T--){
        cin>>b>>a>>d>>e;
        c=(e-d+b)%b;
        ll g=gcd(a,b);
        if(c%g){
            printf("Impossible\n");
            continue;
        }
        a/=g;
        b/=g;
        c/=g;
        exgcd(a,b,x,y);
        x*=c;
        y*=c;
        printf("%lld\n",(x%b+b)%b);
    }
    return 0;
}

[3] 同余方程
题目描述
求关于x的同余方程ax≡1(mod b)的最小正整数解。
输入
每组输入数据只有一行，包含两个正整数a, b，用一个空格隔开。
数据规模：
对于40%的数据，2≤b≤1,000；
对于60%的数据，2≤b≤50,000,000；
对于100%的数据，2≤a, b≤2,000,000,000。
输出
每组输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。
样例输入
3 10
样例输出
7
思路:这题就是求解同余方程

#include<iostream>
#include<cstdio>
#define ll long long 
using namespace std;
ll x,y,m,n,l;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
	if(!b){
		x=1,y=0,d=a;
	}
	else{
		exgcd(b,a%b,d,x,y);
		int t=x;
		x=y;
		y=t-a/b*y;
	}
}
int main()
{
	ll a,b,d,x,y;
	cin>>a>>b;
	exgcd(a,b,d,x,y);
	cout<<(x%b+b)%b<<endl;
	return 0;
}