标书制作教程视频网站,石家庄哪里可以做网站,wordpress 不发送邮件,免费建造网站思路#xff1a;
#xff08;1#xff09;需求#xff1a;求对于1~n中至少能被p1~pm至少1个整除的数的个数#xff0c;由于都是质数#xff0c;彼此互质#xff0c;不需要进行质因子分解#xff0c;根据容斥原理#xff0c; res n/p1 n/p2 ... n/pm - n /(p1p2) -…思路
1需求求对于1~n中至少能被p1~pm至少1个整除的数的个数由于都是质数彼此互质不需要进行质因子分解根据容斥原理 res n/p1 n/p2 ... n/pm - n /(p1p2) - n/(p1p3) - ...
显然只需要讨论p1~pm所有组合形式t如果小于等于n:
如果是奇数个质数组成则加等于n/t,否则减等于n/t
最终结果即为1~n之间的所有至少能被p1~pm之间1个数整除的数的个数。
2注意用二进制讨论组合方式时不能全零全零即为1不满足至少被其中一个整除。
代码
#includebits/stdc.husing namespace std;
const int N 20,M 1 N;
typedef long long LL;LL p[N];int main()
{int n,m;cin n m;for(int i 0;i m;i )cin p[i];LL res 0;for(int i 1;i (1 m);i ){LL t 1,cnt 0;for(int j 0;j m;j ){if(ij 1 1){cnt ;t * p[j];if(t n) break;}}if(t n){if(cnt %2 0) res - n/t;else res n/t;}}cout res endl;return 0;
}
