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

2022-06-16 18:19:44 浏览数 (1)

碎碎念

  • 这是第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

  • 1leq Aleq Bleq 10^{18}
  • 1leq C,Dleq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

代码语言：javascript复制
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

代码语言：javascript复制
4 9 2 3

Sample Output 1

代码语言：javascript复制
2

55 and 77 satisfy the condition.

Sample Input 2

代码语言：javascript复制
10 40 6 8

Sample Output 2

代码语言：javascript复制
23

Sample Input 3

代码语言：javascript复制
314159265358979323 846264338327950288 419716939 937510582

Sample Output 3

代码语言：javascript复制
532105071133627368

题解

小码匠题解

代码语言：javascript复制
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);
}

参考题解

代码语言：javascript复制
#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;
}
division format input output sample

0 人点赞