ABC 253

链接如下

D - FizzBuzz Sum Hard

题意：求1 ~ n中既不是a的倍数也不是b的倍数之和。

题解：正难则反，求不是倍数的和可能比较麻烦，但是求是a和b的倍数好解，于是应用容斥原理，用

1 ~ n的总和 - a的倍数的和 - b的倍数的和 + a与b的倍数的和，则为答案

这里倍数的和可以用等差数列求解，因为不大于n的a的倍数有 n / a个，第一项为a，最后一项为（a * （n / a)）.

所以设有 t  = n / a项，那么a的倍数之和就等于 （a + a * t）* t / 2,提公因数得，(1 + t) * t * a / 2

代码如下

#include 
using namespace std;
long long n;
long long f(long long t)
{

    long long sum = (1 + t) * t / 2;
    return sum;
}
int main(void)
{
    long long a, b;
    cin >> n >> a >> b;
    long long sum = (1 + n) * n / 2;//~n的和

    long long as = f(n / a) * a;//a的倍数和
    long long bs = f(n / b) * b;//b的倍数和
    
    long long ans = sum - as - bs;
    long long lcm = a * b / __gcd(a,b);//a与b的倍数和
    if(lcm <= n)
    {
        ans += f(n / lcm) * lcm;
    }
    cout << ans ;
    return 0;
}