#数论，哈希#洛谷 2429

本文主要是介绍#数论，哈希#洛谷 2429，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

问在$1\dots m$内有多少个数是$p_1,p_2,\dots ,p_n(1\le n\le 20)$的倍数，求这些数的和

---

分析

首先暴力（20!）应该是过不了的，虽然$O(10^{10})$貌似能过，但是还得讲一讲神奇的方法，线性筛，当然同时用哈希维护，然后就没有什么了

---

代码

#include <cstdio>
#include <algorithm>
#define mod 9973//没错，眼见为实
int n,m,prime[21],h[mod],ans;
void in(int &ans){ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
}
void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
int locate(int x){//哈希函数int pos=x%mod,i=0;while (i<mod&&h[(pos+i)%mod]!=x&&h[(pos+i)%mod]) i++;return (pos+i)%mod;
}
int main(){in(n); in(m);for (register int i=1;i<=n;i++) in(prime[i]);std::sort(prime+1,prime+1+n);for (register int i=1;i<=m/prime[1];i++)for (register int j=1;j<=n&&(long long)prime[j]*i<=m;j++){//强制转换（必然）register int pos=locate(prime[j]*i);if (h[pos]!=prime[j]*i){h[pos]=prime[j]*i;ans=(ans+prime[j]*i)%376544743;//统计答案}if (i%prime[j]==0) break;}print(ans);return 0;
}

这篇关于#数论，哈希#洛谷 2429的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---