给出一个数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<cstdio>#include<string.h>#include<queue>#include<vector>#include<algorithm>#define INF 0x3f3f3f3fusing namespace std;typedef long long LL;int main(){ LL n; int p[]={2,3,5,7},u=4; scanf("%lld",&n); LL res=0; for(int i=1;i<1<<u;i++){ int cnt=0;LL cum=1; for(int j=0;j<u;j++){ if(i>>j&1){ cnt++; cum*=p[j]; } } res+=cnt&1?n/cum:-n/cum; } PRintf("%lld/n",n-res); return 0;}新闻热点
疑难解答
