求1-n的阶乘之和

求阶乘之和，以前最开始想到的就是写两个循环，复杂的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;
}

原文链接: https://www.cnblogs.com/Li-ningning/p/13811793.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍