Intermediate.
Put your skills to the test.

Problem summary

Three buses depart at time zero and repeat routes lasting a, b and c minutes. A transfer time is an integer minute when all three depart together. A local day lasts t minutes. Count transfer times during day d, including its first minute and excluding the next day.

Constraints

1 ≤ a, b, c ≤ 10^6; 1 ≤ t, d ≤ 10^9.

Worked example

Original statement sample.

2
3
4
7
2

1

Solution analysis

1. A simultaneous departure must be divisible by all three route lengths. Its period is L = lcm(a,b,c), computed with gcd: lcm(u,v) = u/gcd(u,v) × v. Divide before multiplying.
2. Day d is the integer interval [left,right] = [(d−1)t,dt−1]. The count of nonnegative multiples of L up to right is floor(right/L)+1, including zero. For left > 0 subtract floor((left−1)/L)+1; for left = 0 there is nothing to subtract.
3. For a=2,b=3,c=4, L=12. Day 2 with t=7 is [7,13]. The only multiple of 12 there is 12, so the answer is 1. Both the combined period (at most 10^18) and the day endpoints fit signed 64-bit integers.

Why it works

The least common multiple characterizes exactly the times divisible by every route period. Subtracting the prefix counts removes precisely the departures before the requested day.

Watch out. Time zero belongs to day 1 and must be counted. Do not include time dt in day d. Use long long before multiplying t and d.

An independently written complete program with standard headers.

#include<iostream>
#include<numeric>
using namespace std;
int main(){
    long long a,b,c,dayLength,day;
    cin>>a>>b>>c>>dayLength>>day;
    long long period=a/gcd(a,b)*b;
    period=period/gcd(period,c)*c;
    long long left=(day-1)*dayLength;
    long long right=day*dayLength-1;
    // Include time zero in the prefix of nonnegative multiples.
    long long answer=right/period+1;
    if(left>0){
        answer-=(left-1)/period+1;
    }
    cout<<answer<<'\n';
}