求阶乘之和,以前最开始想到的就是写两个循环,复杂的O(n^2) , 后来再写一道题的时候,看到只走一遍的,复杂的为O(N)的
题目 : 传送门
这个是先用线性筛筛出素数,刚开再怎么算阶乘和的时候,就犯难了。这么大的数,怎么搞
之前的代码:
long long sum = 0; long long sum = 0; for(int i = 1 ; i <= n ; i++){ long long num = 1 ; for(int j = 1 ; j <= i ; j++){ num *= j; } sum += num; }
优化之后可以用:
long long sum = 0; long long num = 1; for(int i = 1 ;i <= 5 ; i++){ num = num * i ; sum += num; } cout<<sum<<endl;
直接降低的很多
附上连接这道的代码:
#include<bits/stdc++.h> using namespace std; #define Max 100000005 typedef long long ll; bool visit[Max]; int prime[10000000]; int k = 0; ll P , sum = 0;; void isprime() { visit[0] = visit[1] = true; for(int i = 2 ; i < Max ; i++){ if(!visit[i]) prime[k++] = i ; for(int j =0 ; j < k && i * prime[j] < Max ; j++){ visit[i*prime[j]] = true; if(i%prime[j]==0) break; } } } int main() { isprime(); int a; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>a; while(a--){ int n ; ll sum = 0 , num = 1; cin>>n>>P; for(int i = 2 ;i <= n ; i++){ num = num * i % P; if(!visit[i]) sum+=num; if(num == 0) break; } cout<<sum%P<<endl; } return 0; }