Codeforces 678 C. Joty and Chocolate(求最大公约数和最小公倍数)

time limit per test 1 second memory limit per test 256 megabytes

数论

Dscription

    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 ≤ 109).

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.

Examples

input

5 2 3 12 15

output

39

input

20 2 3 3 5

output

51

题意：

有n块砖。他们的编号从1-n，如果i%a==0，则将这块砖涂为红色，他可以得到p个巧克力，如果i%b==0，则将这块砖涂为蓝色，他可以得到q个巧克力，问他最终可以得到多少个巧克力；

解题思路：

ans=n/a+n/b-(n/(max(a,b))*max(a,b));

PS

• 求最大公约数

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

完整代码：

//有1到n n个数，如果k%a==0，那么给p元，如果k%b==0，那么给q元
//如果k%a==0&&k%b==0，那么给p元或者q元
//问你最多给多少
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define ll long long
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    ll n,a,b,p,q,sum;
    while(scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&p,&q)!=EOF)
    {
        sum=0;
        ll lcm=(a*b)/gcd(a,b);
        if(p>q)
        {
            sum+=(n/a)*p;
            sum+=(n/b)*q;
            sum-=(n/lcm)*q;
        }
        else
        {
            sum+=(n/b)*q;
            sum+=(n/a)*p;
            sum-=(n/lcm)*p;
        }
        printf("%lld\n",sum);
    }
}