[BZOJ 1477]青蛙的约会
转载请注明出处：http://danihao123.is-programmer.com/
设用时为[tex]t[/tex]，则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。
整理变形得[tex](n-m)t+Lk=x-y[/tex]。
明显需要扩欧求解。注意此题有很多细节，可参见下代码：
/**************************************************************
Problem: 1477
User: danihao123
Language: C++
Result: Accepted
Time:0 ms
Memory:1288 kb
****************************************************************/
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
if(!b)
return a;
else
return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
}
int main(){
ll a,b,c,t,M,k;
ll x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
a=n-m;
b=L;
c=x-y;
k=gcd(a,b);
if(c%k!=0){
cout<<"Impossible"<<endl;
return 0;
}
a/=k;
b/=k;
c/=k;
exgcd(a,b,k,t,M);
t=(((c*t)%b)+b)%b;
if(!t)
t+=b;
cout<<t<<endl;
return 0;
}
Jul 13, 2023 03:35:50 PM
WBBSE 6th Class Syllabus 2024 Pdf File Format helps to get an idea About the Concepts and Topics Taught in class for a Subject During this Academic year 2024, Students will be able to Access the Clickable Download Links From where they can WBBSE 6th Class Syllabus 2024 Download the Syllabus of Bengali, English Medium All Subjects.WBBSE Recently Upload West Bengal 6th Class Syllabus 2024, WBBSE will Organise the Class Public Examinations in April 2024, West Bengal Every Year A Huge Number of Students Appeared for 6th Class Should Check the new Syllabus Details here.