P2429 制杖题
题目描述
求不大于 m 的、 质因数集与给定质数集有交集的自然数之和。
输入输出格式
输入格式：第一行二个整数 n，m。
第二行 n 个整数，表示质数集内的元素 p[i]。
输出格式：一个整数，表示答案，对 376544743 取模。
输入输出样例
输入样例#1：
2 15 3 5
输出样例#1：
60
说明
样例解释：所有符合条件的数为 3,5,6,9,10,12,15 其和为 60。
··· 测试点编号 规模
1 2 3 n*m<=10^7 4 5 n<=2，m<=10^9 6 7 n<=20，m<=10^8 8 9 10 n<=20，m<=10^9 ···
前三个点：n * m <= 1e7
不难想到暴力求解
后七个点：n <= 20,m <= 1e9
容斥+等差数列求和
利用二进制枚举各个数的乘积，利用等差数列求和，容斥原理排除多算的即可
#include#include #include #include #include #include #include inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();} inline int max(int a, int b){ return a > b ? a : b;} inline int min(int a, int b){ return a < b ? a : b;} inline void swap(int &a, int &b){ int tmp = a;a = b;b = tmp;}const int INF = 0x3f3f3f3f; const int MAXN = 2000 + 5; const int MOD = 376544743;long long n,m; long long p[MAXN]; long long ans;int main() {read(n);read(m);for (register long long i = 1 ; i <= n ; ++ i)read(p[i]);if(n * m <= 100000000){for(int i = 1;i <= m;i ++){for(int j = 1;j <= n;j ++){if(!(i % p[j])){ans += i;ans %= MOD;break;}}}printf("%lld", ans % MOD);return 0;}int S = (1 << n);register long long num,cnt,x;register long long niyuan = (MOD + 1)/ 2;for (register long long i = 1 ; i < S ; ++ i){register long long num = 1,cnt = 0,x = 0;for (register long long j = 1, k = i ; k ; ++j, k >>= 1)if (k & 1)num *= p[j],x ++;cnt = m / num;if (x){if (x & 1)ans += (((num * (1 + cnt))%MOD * cnt)%MOD * niyuan) % MOD;elseans -= (((num * (1 + cnt))%MOD * cnt)%MOD * niyuan) % MOD;ans = ans % MOD;}}printf("%lld", ans % MOD);return 0; }