[已解决]大佬帮忙看看顺便讲一下算法

liu123yang

运动会上，两个班级在为场上的运动员鼓掌加油。其中A班的同学每x秒钟鼓掌一次，B班的同学每y秒钟鼓掌一次，每次鼓掌都持续1秒钟。这样的话，在n秒钟之内，共有多少秒的时间有掌声？
x=2,y=3,n=10的情况如下：

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-3-22 20:11:40

liu123yang 发表于 2022-3-22 19:30
超时啊

因为你没有说最大值是多少，如果是超级大的值，这种题目必须说明清楚，因为普通代码行不通的，大多数需要数学知识。试试这个吧，因为我没有参数，所以无法测试对错：

#include <stdio.h>

int gcd (int a, int b) { return !b ? a : gcd(b, a%b); }
int lcm (int a, int b) { return (a / gcd(a, b)) * b; }

int main(){
    
    int x, y, z, n, a, b, sum = 0;
    scanf("%d%d%d", &x, &y, &n);
    
    z = lcm(x, y);
    a = (z/x + z/y - 1)*(n / z);
    b = (n % z)/x + (n % z)/y;
    
    sum = a + b;
    
    printf("%d", sum);
    
    return 0;
}

跳转到最佳答案楼层

傻眼貓咪

#include <stdio.h>

int main(){
        int x, y, n, sum = 0;
        scanf("%d%d%d", &x, &y, &n);
        for(int i = 1; i <= n; i++){
                if(!(i%x) && !(i%y)) sum++;
                else if(!(i%x) || !(i%y)) sum++;
        }
        printf("%d", sum);
        return 0;
}

2 3 10
7

jhq999

傻眼貓咪 发表于 2022-3-22 16:19

借花献佛

#include <stdio.h>

int main(){
        int x, y, n, sum = 0;
        scanf("%d%d%d", &x, &y, &n);
        for(int i = 1; i <= n; i++){
                 if(!(i%x) || !(i%y)) sum++;
        }
        printf("%d", sum);
        return 0;
}

傻眼貓咪

jhq999 发表于 2022-3-22 18:22
借花献佛

真是厉害，被你点醒了

rfl

#include<stdio.h>

int main()
{
    int x, y, n,sn;
    scanf_s("%d %d %d", &x, &y, &n);
    sn = n / x + n / y - n / (x * y);
    printf("%d", sn);

    return 0;
}

liu123yang

rfl 发表于 2022-3-22 18:35
#include

int main()

部分测试集正确

liu123yang

傻眼貓咪 发表于 2022-3-22 16:19

超时啊

傻眼貓咪

liu123yang 发表于 2022-3-22 19:30
超时啊

n 最大是多少？

傻眼貓咪

liu123yang 发表于 2022-3-22 19:30
超时啊

因为你没有说最大值是多少，如果是超级大的值，这种题目必须说明清楚，因为普通代码行不通的，大多数需要数学知识。试试这个吧，因为我没有参数，所以无法测试对错：

#include <stdio.h>

int gcd (int a, int b) { return !b ? a : gcd(b, a%b); }
int lcm (int a, int b) { return (a / gcd(a, b)) * b; }

int main(){
    
    int x, y, z, n, a, b, sum = 0;
    scanf("%d%d%d", &x, &y, &n);
    
    z = lcm(x, y);
    a = (z/x + z/y - 1)*(n / z);
    b = (n % z)/x + (n % z)/y;
    
    sum = a + b;
    
    printf("%d", sum);
    
    return 0;
}

liu123yang

傻眼貓咪 发表于 2022-3-22 19:47
n 最大是多少？

十万呢

傻眼貓咪

liu123yang 发表于 2022-3-23 15:41
十万呢

你可以试试我的代码：我测试一千万，没有问题，不到半秒

2 3 10000000
6666667