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

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
超时啊

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

1. #include <stdio.h>
   
2. 
   
3. int gcd (int a, int b) { return !b ? a : gcd(b, a%b); }
   
4. int lcm (int a, int b) { return (a / gcd(a, b)) * b; }
   
5. 
   
6. int main(){
   
7.    
   
8.     int x, y, z, n, a, b, sum = 0;
   
9.     scanf("%d%d%d", &x, &y, &n);
   
10.    
    
11.     z = lcm(x, y);
    
12.     a = (z/x + z/y - 1)*(n / z);
    
13.     b = (n % z)/x + (n % z)/y;
    
14.    
    
15.     sum = a + b;
    
16.    
    
17.     printf("%d", sum);
    
18.    
    
19.     return 0;
    
20. }

复制代码

跳转到最佳答案楼层

傻眼貓咪

1. #include <stdio.h>
   
2. 
   
3. int main(){
   
4.         int x, y, n, sum = 0;
   
5.         scanf("%d%d%d", &x, &y, &n);
   
6.         for(int i = 1; i <= n; i++){
   
7.                 if(!(i%x) && !(i%y)) sum++;
   
8.                 else if(!(i%x) || !(i%y)) sum++;
   
9.         }
   
10.         printf("%d", sum);
    
11.         return 0;
    
12. }

复制代码

1. 2 3 10
   
2. 7

复制代码

jhq999

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

借花献佛

1. #include <stdio.h>
   
2. 
   
3. int main(){
   
4.         int x, y, n, sum = 0;
   
5.         scanf("%d%d%d", &x, &y, &n);
   
6.         for(int i = 1; i <= n; i++){
   
7.                  if(!(i%x) || !(i%y)) sum++;
   
8.         }
   
9.         printf("%d", sum);
   
10.         return 0;
    
11. }

复制代码

傻眼貓咪

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
超时啊

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

1. #include <stdio.h>
   
2. 
   
3. int gcd (int a, int b) { return !b ? a : gcd(b, a%b); }
   
4. int lcm (int a, int b) { return (a / gcd(a, b)) * b; }
   
5. 
   
6. int main(){
   
7.    
   
8.     int x, y, z, n, a, b, sum = 0;
   
9.     scanf("%d%d%d", &x, &y, &n);
   
10.    
    
11.     z = lcm(x, y);
    
12.     a = (z/x + z/y - 1)*(n / z);
    
13.     b = (n % z)/x + (n % z)/y;
    
14.    
    
15.     sum = a + b;
    
16.    
    
17.     printf("%d", sum);
    
18.    
    
19.     return 0;
    
20. }

复制代码

liu123yang

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

十万呢

傻眼貓咪

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

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

1. 2 3 10000000
   
2. 6666667

复制代码