龙岩网站建设要多,wordpress chuxia主题,华为十大外包公司排名,收费网站模板思路#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;
}
