给出一个数N,求1至N中,有多少个数不是2 3 5 7的倍数。 例如N = 10,只有1不是2 3 5 7的倍数。
Input
输入1个数N(1 <= N <= 10^18)。
Output
输出不是2 3 5 7的倍数的数共有多少。
Input示例
10
Output示例
1
容斥原理,简单暴力
#include<stdio.h>
#include<string.h> #include<iostream> #include<algorithm> using namespace std; int main() { long long n; long long a[20]; while(scanf("%lld",&n)!=EOF) { memset(a,0,sizeof(a)); a[0]=n/2; a[1]=n/3; a[2]=n/5; a[3]=n/7; a[4]=n/(2*3); a[5]=n/(2*5); a[6]=n/(2*7); a[7]=n/(3*5); a[8]=n/(3*7); a[9]=n/(5*7); a[10]=n/(2*3*5); a[11]=n/(3*5*7); a[12]=n/(2*3*7); a[13]=n/(2*5*7); a[14]=n/(2*3*5*7); /*for(int i=0;i<15;i++) { printf("%d ",a[i]); }*/ // printf("\n"); long long ans=n-a[0]-a[1]-a[2]-a[3]+a[4]+a[5] +a[6]+a[7]+a[8]+a[9]-a[10]-a[11]-a[12]-a[13]+a[14]; printf("%lld\n",ans); }版权声明:本文为博主原创文章,未经博主允许不得转载。