【Codeforces Round #395 (Div. 2)】Codeforces 764A Taymyr is calling you

Comrade Dujikov is busy choosing artists for Timofey’s birthday and is

recieving calls from Taymyr from Ilia-alpinist.

Ilia-alpinist calls every n minutes, i.e. in minutes n, 2n, 3n and so

on. Artists come to the comrade every m minutes, i.e. in minutes m,

2m, 3m and so on. The day is z minutes long, i.e. the day consists of

minutes 1, 2, …, z. How many artists should be killed so that there

are no artists in the room when Ilia calls? Consider that a call and a

talk with an artist take exactly one minute. Input

The only string contains three integers — n, m and z

(1 ≤ n, m, z ≤ 104). Output

Print single integer — the minimum number of artists that should be

killed so that there are no artists in the room when Ilia calls.

容易發現需要殺掉的就是 x∗lcm(n,m) 。

#include<cstdio>
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int main()
{
    int m,n,k;
    scanf("%d%d%d",&n,&m,&k);
    printf("%d\n",k/lcm(n,m));
}