潍坊正规网站建设公司,抖音小程序怎么做,wordpress动画主题,西安网站建设市场本专题主要介绍容斥原理。
大家高中的时候肯定接触过韦恩图#xff0c;容斥原理比较通俗的理解就是减去所有可能并加上重叠的部分。
我们直接看公式#xff1a; 知道后#xff0c;我们先看道模板题#xff1a; 下面是AC代码#xff1a;
#includebits/stdc.h
us…本专题主要介绍容斥原理。
大家高中的时候肯定接触过韦恩图容斥原理比较通俗的理解就是减去所有可能并加上重叠的部分。
我们直接看公式 知道后我们先看道模板题 下面是AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int a[6],n;
signed main(){a[0]2;a[1]5;a[2]11;a[3]13;while(cinn){int sum0;for(int i0;i(14)-1;i){int cnt0;int ww1;for(int j0;j4;j){if((ij)11){ww*a[j];cnt;}}if(cnt%20) sumn/ww;else sum-n/ww;}printf(%lld\n,sum);}
}
接下来看一道有趣的题 下面是分析
首先题目应该改为被1只及以上。同时10^4显然不能容斥原理但我们可以借鉴它先减后弥补的思想。
下面是解法十分的巧妙 下面是AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int n,m,x;
mapint,int mp;
int gcd(int a,int b){while(b){int tmpb;ba%b;atmp;}return a;
}
signed main(){scanf(%lld%lld,n,m);for(int i1;i*im;i){if(m%i0){mp[i]0;mp[m/i]0;}}mp.erase(m);for(int i1;in;i){scanf(%lld,x);int yygcd(x,m);for(mapint,int::iterator itmp.begin();it!mp.end();it){if((it-first)%yy0) mp[it-first]1;}}int sum0;for(mapint,int::iterator itmp.begin();it!mp.end();it){if(it-second0) continue;int numm/(it-first);sum((it-first)*(num))*(num-1)/2*(it-second);for(mapint,int::iterator it1it;it1!mp.end();it1){if(it1it) it1;if(it1mp.end()) break;if((it1-first)%(it-first)0) mp[it1-first]-it-second;}}coutsum;
}
