Problem Statement
Find the sum of integers between 1 and N (inclusive) that are not multiples of A or B.
Constraints
- 1≤N,A,B≤109
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A BOutput
Print the answer.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
|
|
The integers between 1 and 10(inclusive) that are not multiples of 3 or 5 are 1,2,4,7 and 8, whose sum is 1+2+4+7+8=22.
Sample 2
| Inputcopy | Outputcopy |
|---|---|
|
|
题意：
题目要求大致是在1到n中，求所以不是A和B倍数的数的和。
思路：
我们可以算出1到n里面所以数的和，之后减去A和B的倍数。
注意！！！
A和B公共的倍数我们减了两次（A一次B一次）。
首先是暴力的解法代码如下：
暴力
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
long long n, a, b, ans=0;
scanf("%lld%lld%lld", &n, &a, &b);
ans = n * (1 + n) / 2;
long long x=0, y=0;
for (int i = 1; x<= n ||y <= n; i++)
{
x =i*a, y =i*b;
if (x <= n)
{
ans-=x;
if (x % b == 0)
{
ans+=x;
}
}
if (y <= n)
{
ans-=y;
}
}
printf("%lld", ans);
}但是！！！这样写会超时，所以我们应该换一种思路
优化
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long num, nu;
long long gcd(long long a, long long b)
{
return a % b ? gcd(b, a % b) : b;
}
long long sum(long long x, long long y)
{
return y*(x+y*x)/2;
}
int main()
{
long long n, a, b, ans = 0;
scanf("%lld%lld%lld", &n, &a, &b);
long long bei = a * b / gcd(a, b);
ans = n * (1 + n) / 2;
num = n/a;
nu = n/b;
ans -= sum(a, num);
ans -= sum(b, nu);
for (int i = 1; i <= n; i++)
{
if (i * bei > n)
break;
ans += (i * bei);
}
printf("%lld", ans);
}