刷题总结(1)

题目描述

给出一个数n，求1到n中，有多少个数不是2 5 11 13的倍数。

输入描述

本题有多组输入每行一个数n，1<=n<=10^18.

输出描述

每行输出输出不是2 5 11 13的倍数的数共有多少。

示例

输入

15

输出

4

AC代码

#include <stdio.h>
int main()
{
    long n;
    while(~scanf("%ld",&n)) //该处是牛客网oj处理多组输入时需要加的
    {
        long long a1 = n / 2 + n / 5 + n / 11 + n / 13; //2、5、11、13倍数的个数
        long long a2 = n / 10 + n / 22 + n / 26 + n / 55 + n / 65+ n / 143;//(2,5)、(2,11)、(2,13)、(5,11)、(5,13)、(11,13)两数倍数的个数
        long long a3 = n / 110 + n / 130 + n / 286 + n / 715;   //(2,5,11)、(2,5,13)、(2,11,13)、(5,11,13)三数倍数的个数
        long long a4 = n / 1430;    //(2,5,11,13)四数倍数的个数
        long a = a1 - a2 + a3 - a4; //该句理解见文章最后
        printf("%ld\n",n - a);
    }
    return 0;
}

总结

开始做这道题时，想着直接遍历1~n，然后依次判断不能整除2、5、11、13，则计数器加1，实现如下：

int count = 0;
for(int i = 0; i < n; i++)
{
    if((i%2!=0)&&(i%5!=0)&&(i%11!=0)&&(i%13!=0))
    {
        count++;
    }
}

但是这种方法的复杂度为，在牛客网oj时超时，不能通过，所以换成了如上方法。

对于表达式a1-a2+a3-a4的理解：

2	5	11	13
2	5	11	13
4	10
6	15
8
10
12
14

如上是当n为15时，各个数的倍数，由上面可知

a1 = 7 + 3 + 1+ 1

但仔细观察便可发现其中10算了两次，10即是2的倍数又是5的倍数，所以必须减去一次两数倍数，这便有了a2

a2 = 1 + 0 + 0 + 0 + 0 + 0

于是有a1 - a2，同理可推测整个式子。