容斥定理 AtCoder——FizzBuzz Sum Hard

题目传送门

Problem Statement

Find the sum of integers between <var>1</var> and <var>$N$</var> (inclusive) that are not multiples of <var>$A$</var> or <var>$B$</var>.

Constraints

• <var>1≤N,A,B≤10⁹ </var>
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print the answer.

Sample 1

10 3 5

22

The integers between <var>1</var> and <var>10</var>(inclusive) that are not multiples of <var>3</var>&nbs***bsp;<var>5</var> are <var>1,2,4,7</var> and <var>$8$</var>, whose sum is <var>1+2+4+7+8=22</var>.

Sample 2

1000000000 314 159

495273003954006262

题意：

题目要求大致是在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);
}