| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 133905 | Accepted: 29707 |
Description
Input
Output
Sample Input
1 2 3 4 5
Sample Output
4
题解：假设A的起始位置为A，A的步长为a;B的起始位置为B，步长为b，地球赤道周长为L;运动t次后A,B相遇；则：
A的运动方程为 ：A+at;
B的运动方程为 ：B+bt;
相遇条件为 ：A+at-B-bt=mL;
移项整理得 ：(b-a)t+mL=A-B;
所以很明显，这是一道用扩展欧几里得解不定项的问题，因为用扩展欧几里得解得的x只是满足方程的一个解，不一定是符合题意的最优解，所以最后的结果要取最小正整数解
#include<iostream> #include<math.h> #define max 0x3f3f3f3f #define ll long long #define mod 1000000007 using namespace std; ll x,y,r,s; void exgcd(ll a, ll b, ll &x, ll &y) //拓展欧几里得算法 { if(!b) x = 1, y = 0; else { exgcd(b, a % b, y, x); y -= x * (a / b); } } ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } void T(ll a,ll b,ll c) { r=gcd(a,b); s=b/r; exgcd(a,b,x,y);//得到x0 x=x*c/r; //得到x1 x=(x%s+s)%s; //得到最小正整数解 } int main() { ll A,B,L,a,b,r,c; scanf("%lld%lld%lld%lld%lld",&A,&B,&a,&b,&L); r=gcd(b-a,L),c=A-B; if(c%r!=0||a==b) printf("Impossible\n"); else { T(b-a,L,A-B); printf("%ld\n",x); } return 0; }
原文：https://www.cnblogs.com/-citywall123/p/10680585.html