[BZOJ 1477]青蛙的约会

danihao123 posted @ 2016年8月28日 19:59 in 题解 with tags BZOJ tyvj 扩展欧几里得算法 , 597 阅读
转载请注明出处: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;
}
WBBSE 6th Class Syl 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter