欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

宽容原则 原则和模板代码

最编程 2024-07-05 08:10:12
...
//题目背景:AcWing 890 #include<iostream> using namespace std; typedef long long LL; const int N=20; int n,m,p[N]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d",&p[i]); //读入所有质数 int res=0;//存储总数 for(int i=1;i<1<<m;i++) //枚举1~2的m次方-1,每个数的m位二进制表示,表示了一种选择的情况 { int t=1; //一种情况下选中的质数的乘积,即它们的最小公倍数 int s=0; //一种情况下选中了几个数 for(int j=0;j<m;j++) //遍历当前遍历到的这个数的m位中的每一位 计算选中情况 { if(i>>j&1) //如果当前位为1,证明选中了它 { if((LL)t*p[j]>n) //但是如果这个时候公倍数已经大于n了,说明1~n中不含有同时能整除这几个选中的质数的数 { t=-1; //t=-1作为退出标记 break; //退出内层循环 } t=(LL)t*p[j]; //如果不是上述情况,就把选中的质数乘到t上去 s++; //选中数量++ } } if(t==-1) continue; //识别到退出标记,continue继续循环 if(s&1) res+=n/t; //如果当前这个数反映的选择情况是选择了奇数个,则作加法 else res-=n/t; //是偶数,作减法 } printf("%d",res); return 0; }

推荐阅读