Project Euler 6-10题

为什么感觉6-10题比1-5题暴力了好多，没什么好的可改进点-_-!!!

第6题

题目来源ProjectEuler

这个题求(∑ni=1i)2−(∑ni=1i2)，是O(1)的。

int main(){
    long long ans=0,n=100;
    ans=n*(n+1)/2;
    ans*=ans;
    ans-=n*(n+1)*(2*n+1)/6;
    cout<<ans<<endl;
    return 0;
}

此外： ∑ni=1i3=(∑ni=1i)2=n∗(n+1)/2

第7题

题目来源ProjectEuler
这个题是求第10001个素数。
关于小于N的素数的个数，有这么一个估计公式：π(N)≈Nln(N)
详情可参考*
考虑到lnx≈lnxlnx所以第10001个素数大小大概为10001∗ln(10001)≈132878，跟答案在一个数量级内。
而求素数算法中，有一个近似线性时间（在O(n)−O(nlogn)之间）内求出所有小于n的素数的算法，叫线性筛，也叫欧拉筛。

int prime[10000000],cnt;
int num[10000000];

int main(){
    cnt=0;int n=10000000-1;
    for(int i=2;i<=n;i++){
        if(num[i]==0)   prime[++cnt]=i;
        for (int j=1;j<=cnt&&i*prime[j]<=n;j++){
            num[i*prime[j]]=1;
        }
    }
    cout<<prime[10001]<<endl;
    return 0;
}

大致思路是这样的，我们从2-n依次选择一个数i，若i未被标记，我们将其加入到素数队列中。若i未被标记为合数，则将其加入到素数队列中去。然后对于i，我们将i的所有已知素数倍的且小于n的结果标为合数。
因为每个合数x都可以表示为x=k∗p,k≥p，其中p是素数。（若k<p，则k一定有一个<p的素因子p′）。在上述代码中，x会在当i==k，prime[j]==p时，被标记。

复杂度f(n)计算方法为O(n)<f(n)=∑ni=2min(π(i),ni)<∑ni=2ni≈nlnn

第8题

题目来源ProjectEuler

这个题是给你一千个数字，求最大的连续13个数字的积。
分析一下可以发现，如果这13个数字中有一个0，那么这个结果肯定不能要。
那么我们的策略就显然了，我们先令ans=0，记录一下当前的product是连续cnt个非零数字的积。那么当cnt==13的时候，我们将product除掉第一个数字，乘上现在这个数字，得到一个新的product，ans更新为product和ans的最大值；当cnt<13的时候，我们将product直接乘上当前这个数字，并且cnt++。在结束当前循环前，判断product是否为0，若product==0，则将cnt归零。
复杂度O(n+len)

char s[1050];

int main(){
    for (int i=0;i<20;i++){
        scanf("%s",s+i*50);
    }
    int len=13;long long ans=0,product=1,cnt=0;
    for(int i=0;i<1000;i++){
        if (cnt<len){
            product*=(s[i]-'0');
            cnt++;
        }
        else{
            product/=(s[i-len]-'0');
            product*=(s[i]-'0');
            ans=max(ans,product);
        }
        if (product==0){
            product=1;
            cnt=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

第9题

题目来源ProjectEuler

这个是求a,b,c，满足a2+b2=c2且a+b+c=1000
枚举a,b，令c=1000-a-b，判断a2+b2=c2是否成立，成立则输出并退出程序。
因为c>max(a,b)所以a,b只需要枚举到500就可以了。
输出a,b,c可以看到2002+3752=4252

int main(){
    for (int a=1;a<500;a++){
        for (int b=1;b<500;b++){
            int c=1000-a-b;
            if (a*a+b*b==c*c){
                printf("%d %d %d %d\n",a,b,c,a*b*c);
                return 0;
            }
        }
    }
}

第10题

题目来源ProjectEuler

这里是求所有小于2,000,000的素数的和，使用第7题里面的线性筛，求和即可。

int prime[10000000],cnt;
int num[10000000];

int main(){
    cnt=0;int n=10000000-1;
    for(int i=2;i<=n;i++){
        if(num[i]==0)   prime[++cnt]=i;
        for (int j=1;j<=cnt&&i*prime[j]<=n;j++){
            num[i*prime[j]]=1;
        }
    }
    long long ans=0;
    for (int i=1;i<=cnt;i++){
        if (prime[i]<2000000) ans+=prime[i];
        else break; 
    }
    cout<<ans<<endl;
    return 0;
}