求不大于 m 的、 质因数集与给定质数集有交集的自然数之和。
第一行二个整数 n，m。
第二行 n 个整数，表示质数集内的元素 p[i]。
一个整数，表示答案，对 376544743 取模。
2 15 3 5
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 ···
单个容斥+等差数列求和会TLE三个点
而且为什么1算质数？？？
#include<cstdio> #include<iostream> #pragma GCC optimize(3) #pragma GCC optimize(2) using namespace std; inline int read() { int x=0; char ch=getchar(); char c=ch; while(ch>‘9‘||ch<‘0‘)c=ch,ch=getchar(); while(ch<=‘9‘&&ch>= ‘0‘)x=x*10+ch-‘0‘,ch=getchar(); if(c==‘-‘)x=x*-1; return x; } void put(long long f) { if(f<0)putchar(‘-‘),f=-f; int top=0,q[20]; while(f)q[++top]=f%10,f/=10; top=max(top,1); while(top--)putchar(‘0‘+q[top+1]); } long int n,m,i,j,a[505]; long long ans=0; int tot=376544743; bool b[1000000005]; int main(){ n=read(); m=read(); for(i=1;i<=n;i++){ a[i]=read(); if(a[i]==1){ for(j=1;j<=m;j++){ ans+=i; } put(ans%tot);; return 0; } } for(i=1;i<=n;i++){ if(a[i]<=m){ for(j=1;j*a[i]<=m;j++){ if(b[a[i]*j]==false){ b[a[i]*j]=true; } } } } for(i=1;i<=m;i++){ if(b[i]==true){ ans+=i; } } put(ans%tot); return 0; }
原文：https://www.cnblogs.com/hrj1/p/11143216.html