HPU1434: Neo 的代码优化

1434: Neo 的代码优化

时间限制: 1 Sec 

内存限制: 128 MB

提交: 20 

解决: 6 

​​统计​​

题目描述

#include<stdio.h>

int main()
{
    int a, b, c, n;
    while(scanf("%d%d%d%d", &a, &b, &c, &n) != EOF) {
        int res = 0;
        for(int i = 1; i <= n; ++i) {
            if(i % a == 0 || i % b == 0 || i % c == 0) {
                ++res;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}      

Neo 认为这段代码运行得太慢了，想让你优化这段代码。

输入

输入格式和上面代码保持一致。

保证输入的a,b,ca,b,c 都是素数，且 1<a,b,c,n<=1091<a,b,c,n<=109

输出

输出格式和上面代码保持一致。

样例输入

2 3 5 100
3 5 7 100      

样例输出

74
55      

来源

​​LZ​​

提交

​​讨论​​

/*
  这个问题看看代码就知道是求从1到n单位内
    a的倍数 
    b的倍数 
    c的倍数 
  的数一共有多少个 
  
  
  一定要记得减去重复的数字，因为有可能有的数字是它们共同的倍数 
*/

#include<cstdio>
typedef long long ll;
int main()
{
  ll a,b,c,n;
  while(scanf("%lld %lld %lld %lld",&a,&b,&c,&n)!=EOF)
  {
    printf("%lld\n",n/a+n/b+n/c-n/(a*b)-n/(a*c)-n/(b*c)+n/(a*b*c));
  }
  return 0;
}