CodeForces-678C: Joty and Chocolate（LCM）

数论

Description

Little Joty has got a task to do. She has a line of n tiles indexed from 1 to n. She has to paint them in a strange pattern.

An unpainted tile should be painted Red if it's index is divisible by a and an unpainted tile should be painted Blue if it's index is divisible by b. So the tile with the number divisible by a and b can be either painted Red or Blue.

After her painting is done, she will get p chocolates for each tile that is painted Red and q chocolates for each tile that is painted Blue.

Note that she can paint tiles in any order she wants.

Given the required information, find the maximum number of chocolates Joty can get.

Input

The only line contains five integers n, a, b, p and q $(1 ≤ n, a, b, p, q ≤ 10^9)$.

Output

Print the only integer s — the maximum number of chocolates Joty can get.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Sample Input

5 2 3 12 15
20 2 3 3 5

Sample Output

39
51

题意：输入n，a，b，p，q，从1到n中找到a的倍数，b的倍数，a和b共同的倍数。a的倍数个数乘以p，b倍数个数乘以q，共同倍数的个数乘以p和q中的最大值，得到结果。

分析： a和b的倍数个数就是用n除以他们取整，当中可能有重复的，就是a和b共同的倍数。先找到a和b的最小公倍数，n除以它得到共同倍数的个数，ab倍数个数减去共同倍数的个数= =好绕

• 完整代码：

#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
LL gcd(LL a,LL b) //辗转相除法求最大公因数
{
    LL t;
    while(b)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int main()
{
    LL n,a,b,p,q,lcm;
    LL x1,x2,x3;
    while(scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&p,&q)!=EOF)
    {
        x1=n/a;
        x2=n/b;
        lcm=a*b/gcd(a,b);
        x3=n/lcm;
        x1-=x3;
        x2-=x3;
        printf("%lld\n",x1*p+x2*q+x3*max(p,q));
    }
    return 0;
}