【小码匠自习室】ABC131-C: 第n个悲伤的故事

小码匠

发布于 2022-06-16 18:19:44

2940

发布于 2022-06-16 18:19:44

文章被收录于专栏：小码匠和老码农

碎碎念

这是第n个悲伤的故事……
今天，我将代码的正负号搞错了（老码农：和你刷数学题一样）然后，代码就WA了，结果测试时还挺好，一正式提交就挂，所以，我学会了，要多造点测试样例
一定有朋友注意到了，我的代码一个字乱，两个字太乱……咳咳，所以，以后呐，我要多写函数，多多益善

题目地址

C - Anti-Division
- https://atcoder.jp/contests/abc131/tasks/abc131_c?lang=en

题目描述

Problem Statement

You are given four integers A, B, C, and D. Find the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

Constraints

1\leq A\leq B\leq 10^{18}
1\leq C,D\leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of integers between A and B (inclusive) that can be evenly divided by neither C nor D.

Sample Input 1

4 9 2 3

Sample Output 1

55 and 77 satisfy the condition.

Sample Input 2

10 40 6 8

Sample Output 2

Sample Input 3

314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

532105071133627368

题解

小码匠题解

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long a, b, c, d, e, f, g, h;
    cin >> a >> b >> c >> d;
    if(a % c == 0) {
        e = a / c - 1;
    } else {
        e = a/ c;
    }
    if (a % d == 0) {
        f = a / d - 1;
    } else {
        f = a / d;
    }
    g = d * c / __gcd(d, c);
    if (a % g == 0) {
        h = a / g - 1;
    } else {
        h = a / g;
    }
    cout << b - a + 1 - (b / c - e) - (b / d - f) + (b / g - h);
}

参考题解

#include <iostream>
using namespace std;

long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }
long long num(long long n, long long c, long long d) {
    long long G = GCD(c, d);
    long long L = c / G * d;
    return n - n / c - n / d + n / L;
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << num(b, c, d) - num(a-1, c, d) << endl;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除

division