P2429 制杖题

题目描述

求不大于 m 的、 质因数集与给定质数集有交集的自然数之和。

输入输出格式

第一行二个整数 n，m。

第二行 n 个整数，表示质数集内的元素 p[i]。

一个整数，表示答案，对 376544743 取模。

输入输出样例

2 153 5

60

说明

样例解释：所有符合条件的数为 3,5,6,9,10,12,15 其和为 60。

··· 测试点编号 规模

1 2 3 n*m<=10^74 5 n<=2，m<=10^96 7 n<=20，m<=10^88 9 10 n<=20，m<=10^9···

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring> #include <algorithm>#include <vector>#include <queue>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;            else                ans -= (((num * (1 + cnt))%MOD * cnt)%MOD * niyuan) % MOD;            ans = ans % MOD;        }    }    printf("%lld", ans % MOD);    return 0;}