传送门:https://loj.ac/problem/6165
这题“一道水题”,一道非常难的数学题。(主要是我不会线性筛)
先来讲一下线性筛(欧拉筛法):
我们从2一直找到\(n\),如果这个数没有被标记为非质数,就把它放进一个记录目前找到的所有质数的数组\(prime\)里面,并且用\(pri\)这个数记录下当前有多少个质数。
然后我们把从\(prime[1]\)到\(prime[pri]\)和当前的数\(i\)的乘积标记为非质数,如果乘积超过\(n\)就结束循环。
慢着,这不是和普通筛法一样?关键的来了!!!
这是线性筛中非常关键的一行代码:
1 |
if(i % prime[j] == 0) break; |
正是它,使得这种筛法变为线性的。
因为如果\(i\)是\(prime[j]\)的倍数,那么之前在删\(prime[j]\)和别的数的乘积的时候肯定已经把\(i\)的倍数删掉了。如果不好理解,可以自己模拟一下。
这样,每个合数都会被删掉,并且不会被重复删掉。这使得它的复杂度成为线性的了。
普通筛法——埃拉托斯特尼筛法的时间复杂度为\(O(n\ log\ log\ n)\),空间复杂度为\(O(n)\)。如果数据中\(n\)达到了\(10^8\)(比如现在讲的这题),那么就会超时。
这种筛法——欧拉筛法的时间复杂的为\(O(n)\)。
讲完线性筛,再来讲讲这题的做法。
这题是要求\([1,n]\)中所有数的最小公倍数模\(10^8+7\)的值,其实也就是求每一个数分解质因数后,把所有质数的次数取最高次然后乘起来。例如题目样例,\(1\sim 10\)中,2的最高次是3(\(8=2^3\)),3的最高次是2(\(9=3^2\)),5的最高次是1,7的最高次也是1,那么最终的答案为\(2^3\times 3^2\times 5\times 7=2520\)。
我们在筛每一个质数\(i\)的之前,就可以先计算出它的最高次应该是多少(即使得\(i^t\leq n\)的最大的\(t\)),然后把它乘进\(ans\)中并对\(10^8+7\)取模即可(初始化\(ans=1\))。
这样做时间复杂度当然是\(O(n)\)的,但是由于有常数,并且时间限制只有\(1s\),我们还需要进行常数上的优化。由于空间限制只有\(128MB\),我们一定要注意空间问题。(我也不知道我是怎么把它优化到时空限制都符合要求的,反正我的原则是:能不开long long就不开long long,能不把变量开在循环里面就不把变量开在循环里面。再加上可能LOJ评测机的速度比较可观,就愉快地AC啦~)其实我优化了好久的QAQ。。。
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int MAXN = 1e8 + 10; const int mod = 1e8 + 7; int n,k; bool isprime[MAXN]; int prime[5761500]; int pri = 0; int ans; ll t; int main() { scanf("%d",&n); memset(isprime,1,sizeof isprime); ans = 1; for(int i = 2; i <= n; ++i) { if(isprime[i]) { prime[++pri] = i; t = i; while(t*i<=n) t*=i; ans = (ans*t)%mod; } for(int j = 1; j <= pri; ++j) { k = i*prime[j]; if(k>n)break; isprime[k] = 0; if(i % prime[j] == 0) break; } } printf("%d\n",ans); return 0; } |