cfgym101252E

201707 （ACM）数学

题意

题解

• 31行之前的代码是一开始就想到的，但是还要考虑在城市相遇的情况。
• 假设$t$时刻在同一个城市相遇，那么$v1×t=x×l$，$v2×t=y×l$，$x,y$互质并且一奇一偶时第一次相遇。之后的每次相遇奇偶相等。
• $\frac{v1×t}{v2×t}=\frac{x×l}{y×l}$。$\frac{x}{y}$的最简单整数比就是$\frac{v1/d}{v2/d}$，（$d=gcd(v1,v2)$）。若这个比值是一奇一偶，那么一倍是是一奇一偶，之后的三倍，五倍$...$时奇偶性相等。
• $x$的最大取值是$\frac{v1*T}{l}$，最多能取到$k=\frac{(v1*T)/l}{(v1/d)}$倍。
• 然后算一下就行了。

总结

• 比赛时候其实就差了一点点，还是要冷静下来好好想一下。

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
//-----------
ll gcd(ll a,ll b){return (b==0)?a:gcd(b, a%b);}
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ll l,v1,v2,t;
    while(~scanf("%lld%lld%lld%lld",&l,&v1,&v2,&t)) {
        if(v1<v2) swap(v1,v2);
        ll a=v1*t,b=v2*t;
        ll x=a/l,y=b/l;
        ll xx=a%l,yy=b%l;
        ll ans=x;
        ll fa=x%2,fb=(y+1)%2;
        if(fa==fb) {
            if(xx>=yy) ++ans;
        } else {
            if(xx+yy>=l) ++ans;
        }
        ll d=gcd(v1,v2);
        v1/=d;v2/=d;
        ll k=min(x/v1,y/v2);
        if((v1+v2)&1) ans-=(k+1)/2;
        printf("%lld\n",ans);
    }
    return 0;
}