ABC 253 |
您所在的位置：网站首页 › 1是不是10的倍数怎么算 › 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 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |