problem 29

不同的幂

考虑所有满足2 ≤ a ≤ 5和2 ≤ b ≤ 5的整数组合生成的幂ab:

$2^2=4,2^3=8,2^4=16,2^5=32$

$3^2=9,3^3=27,3^4=81,3^5=243$

$4^2=16,4^3=64,4^4=256,4^5=1024$

$5^2=25,5^3=125,5^4=625,5^5=3125$

如果把这些幂按照大小排列并去重,我们得到以下由15个不同的项组成的序列:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

在所有满足2 ≤ a ≤ 100和2 ≤ b ≤ 100的整数组合生成的幂ab排列并去重所得到的序列中,有多少个不同的项?


考虑做一个简单的容斥。

首先考虑在什么情况下会有重复的幂出现。

在100以内,当且仅当这个数能够被分解为唯一的$a^b$时。

这个a不一定是质数,所以需要讨论一下会有哪些数作为底数。

很明显,$a^b\leq 100,b\ge 2$。

那么$a\leq 10$。所以初步确定a=[2,10]。

但是又有$4=2^2,8=2^3,9=3^2$,所以把这三个数去掉,a的可能取值为 2,3,5,6,7,10

考虑用它们中的每一个作底数$a$可以分别生成多少个不同的$a^b$,这个可以用set实现。

那么就可以得到6个值。我们把它们累加至$sum$。

再思考一下$sum$的含义,它们是所有以 2,3,5,6,7,10为底数的$a^b$个个数,那么能用这几个$a$单独生成,也就是$a^x=a'$的底数$a'$也会被$a^b$所囊括。

所以它们代表了 2,3,4,5,6,7,8,9,10,16,25,36,49,64,81,100的答案,共18个数。

初始答案就是a,b的组合,也就是$(n-1)^2$,用它减去$18*(n-1)$再加上上述计算出的$sum$就是最终的答案了。

code

#include<bits/stdc++.h>
using namespace std;
int n=100;
int fac[7]={0,2,3,5,6,7,10};
//后出现的数,即重复的数化为a^b的形式,fac存的是a可能的值。
//b>=2,a<=10。 
//这些数的幂在100以内有2,3,4,5,6,7,8,9,10,16,25,36,49,64,81,100,故最后减去 
int main()
{
    int ans=(n-1)*(n-1);//初始答案为(n-1)^2 
    set<int> s;
    for(int p=1;p<=6;p++)
    {
        int f=fac[p];
        for(int i=1;pow(f,i)<=n;i++)//枚举可能出现的重复的数f^i
            for(int j=2;j<=n;j++)//(f^i)^j=f^(i*j)即可能出现的重复情况,将不同的指数去重 
                s.insert(i*j);
        ans+=s.size();//这就是剩下对于f的不同的指数个数
        s.clear();
    }
    printf("%d\n",ans-18*(n-1));
    //即f=2,3,4,5,6,7,8,9,10,16,25,36,49,64,81,100时 
    //减去100以内以fac的幂为底数的初始答案 
    return 0;
}


Problem 30

各位数字的五次幂

令人惊讶的是,只有三个数可以写成它们各位数字的四次幂之和:

1634 = $1^4+6^4+3^4+4^4$
8208 = $8^4+2^4+0^4+8^4$
9474 = $9^4+4^4+7^4+4^4$

由于1 = 14不是一个和,所以这里并没有把它包括进去。

这些数的和是1634 + 8208 + 9474 = 19316。

找出所有可以写成它们各位数字的五次幂之和的数,并求这些数的和。


从10枚举到1e6即可。

code


#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n=5,ans=0;
    for(int i=10;i<=999999;i++)
    {
        int tmp=i,t=0;
        while(tmp)
            t+=pow((tmp%10),n),tmp/=10;
        if(t==i)ans+=i;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 31

硬币求和

英国的货币单位包括英镑£和便士p,在流通中的硬币一共有八种:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)

以下是组成£2的其中一种可行方式:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

不限定使用的硬币数目,组成£2有多少种不同的方式?


一维费用的背包问题。

O(nm)暴力找就完了。

code


#include<bits/stdc++.h>
using namespace std;
int v[9]={0,1,2,5,10,20,50,100,200};
int n=8,m=200;
int f[210];
int main()
{
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
            f[j]+=f[j-v[i]];
    printf("%d\n",f[m]);
}


Problem 32

全数字的乘积

如果一个n位数包含了1至n的所有数字恰好一次,我们称它为全数字的;例如,五位数15234就是1至5全数字的。

7254是一个特殊的乘积,因为在等式39 × 186 = 7254中,被乘数、乘数和乘积恰好是1至9全数字的。

找出所有被乘数、乘数和乘积恰好是1至9全数字的乘法等式,并求出这些等式中乘积的和。

注意:有些乘积可能从多个乘法等式中得到,但在求和的时候只计算一次。


暴力枚举a*b=c,判断是否符合条件。

code


#include<bits/stdc++.h>
using namespace std;
int vis[10000];
int main()
{
    int v[11],ans=0,n=2000;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            int c=i*j,a=i,b=j,f=1;
            memset(v,0,sizeof v);
            while(a)v[a%10]++,a/=10;
            while(b)v[b%10]++,b/=10;
            while(c)v[c%10]++,c/=10;
            if(v[0])f=0;
            for(int p=1;p<=9&&f;p++)
                if(v[p]!=1)f=0;
            if(f&&!vis[i*j])
                vis[i*j]=1,ans+=i*j;
        }
    printf("%lld\n",ans);
    return 0;
}


Problem 33

消去数字的分数

49/98是一个有趣的分数,因为缺乏经验的数学家可能在约简时错误地认为,等式49/98 = 4/8之所以成立,是因为在分数线上下同时抹除了9的缘故。

我们也会想到,存在诸如30/50 = 3/5这样的平凡解。

这类有趣的分数恰好有四个非平凡的例子,它们的分数值小于1,且分子和分母都是两位数。

将这四个分数的乘积写成最简分数,求此时分母的值。


暴力枚举$\frac{a}{b}$,再依照题目描述加上一个数字判断分数值是否相等。

最后把得到的分子分母相乘再约分就好了。

code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int f1=1,f2=1;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++)
            for(int k=1;k<=9;k++)
            {
                int fz=i*10+k,fm=k*10+j;
                if((double)i/j<1&&(double)i/j==(double)fz/fm)f1*=fz,f2*=fm;
            }
    f2/=__gcd(f1,f2);
    printf("%d\n",f2);
    return 0;
}


Problem 34

各位数字的阶乘

145是个有趣的数,因为1! + 4! + 5! = 1 + 24 + 120 = 145。

找出所有各位数字的阶乘和等于其本身的数,并求它们的和。

注意:因为1! = 1和2! = 2不是和的形式,所以它们并不在讨论范围内。


枚举就完事了。

code


#include<bits/stdc++.h>
using namespace std;
int fac[11];
int main()
{
    int ans=0;
    fac[0]=1;
    for(int i=1;i<=9;i++)
        fac[i]=fac[i-1]*i;
    for(int i=10;i<=100000;i++)
    {
        int tmp=i,t=0;
        while(tmp)
            t+=fac[tmp%10],tmp/=10;
        if(t==i)ans+=i;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 35

圆周素数

197被称为圆周素数,因为将它逐位旋转所得到的数:197/971和719都是素数。

小于100的圆周素数有十三个:2、3、5、7、11、13、17、31、37、71、73、79和97。

小于一百万的圆周素数有多少个?


暴力旋转判质数。

code

#include<bits/stdc++.h>
using namespace std;
int a[8];
inline bool check(int num)
{
    if(num==1||(num%6!=1&&num%6!=5))return 0;
    if(num==2||num==3)return 1;
    int tmp=sqrt(num);
    for(int i=5;i<=tmp;i+=6)
        if(num%i==0||num%(i+2)==0)
            return 0;
    return 1;
}
int main()
{
    int n=7,ans=-1;
    for(int i=1;i<=n;i++)
        a[i]=i;
    do
    {
        int k=0;
        for(int i=1;i<=n;i++)
            k=(k<<3)+(k<<1)+a[i];
        if(check(k))ans=max(ans,k);
    }
    while(next_permutation(a+1,a+1+n));
    printf("%d\n",ans);
    return 0;
}


Problem 36

双进制回文数

十进制数$585 = 1001001001_2$(二进制表示),因此它在这两种进制下都是回文数。

找出所有小于一百万,且在十进制和二进制下均回文的数,并求它们的和。

(请注意,无论在哪种进制下,回文数均不考虑前导零。)


暴力模拟就好了。

code


#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
inline bool hw(int x)
{
    int res=0;
    while(x>res)
        res=(res<<3)+(res<<1)+x%10,x/=10;
    return (x==res||x==res/10);
}
signed main()
{
    int n=1000000,ans=0;
    for(int i=1;i<=n;i+=2)
    {
        if(i%10==0)continue;
        int k=0,a=i;
        while(a)
            k=(k<<3)+(k<<1)+(a&1),a>>=1;
        if(hw(i)&&hw(k))
            ans+=i;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 37

可截素数

3797有着奇特的性质。不仅它本身是一个素数,而且如果从左往右逐一截去数字,剩下的仍然都是素数:3797、797、97和7;同样地,如果从右往左逐一截去数字,剩下的也依然都是素数:3797、379、37和3。

只有11个素数,无论从左往右还是从右往左逐一截去数字,剩下的仍然都是素数,求这些数的和。

注意:2、3、5和7不被视为可截素数。


模拟判断。

code


#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int st[N],pr[N],cnt;
void prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])st[i]=2,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++)
        {
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int main()
{
    prime(N-10);
    int n=1000000,ans=0;
    for(int i=8;i<=n;i++)
    {
        int a=i,f=1,b=0,l=0;
        while(a&&f)
        {
            if(st[a]!=2)f=0;
            a/=10;
        }
        a=i;
        while(a&&f)
        {
            b=b+a%10*pow(10,l++);
            a/=10;
            if(st[b]!=2)f=0;
        }
        if(f)ans+=i;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 38

全数字的倍数

将192分别与1、2、3相乘:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

连接这些乘积,我们得到一个1至9全数字的数192384576。我们称192384576为192和(1,2,3)的连接乘积。

同样地,将9分别与1、2、3、4、5相乘,得到1至9全数字的数918273645,即是9和(1,2,3,4,5)的连接乘积。

对于n > 1,所有某个整数和(1,2, … ,n)的连接乘积所构成的数中,最大的1至9全数字的数是多少?


发现对于每个n我们可以确定一个唯一的区间[l,r]使得这个区间里的数和n的连接成绩保持在9位。

并且当n=8,9时是无解的。

那么就模拟一下就好了。

code

#include<bits/stdc++.h>
using namespace std;
int a[8][2]={0,0,0,0,5000,9999,100,333,25,33,5,9,3,3,2,2};
inline int len(int x)
{
    int l=0;
    while(x)l++,x/=10;
    return l;
}
inline bool check(int x)
{
    int f=0;
    while(x)f|=(1<<(x%10)),x/=10;
    return (f==(1<<10)-2);
}
int ans=-1;
int main()
{
    for(int n=2;n<=7;n++)
    {
        for(int i=a[n][0];i<=a[n][1];i++)
        {
            int res=0;
            for(int j=1;j<=n;j++)
                res=(res*pow(10,len(i*j)))+i*j;
            if(check(res))ans=max(ans,res);
        }
    }
    printf("%d\n",ans);
    return 0;
}


Problem 39

整数边长直角三角形

若三边长{a,b,c}均为整数的直角三角形周长为p,当p = 120时,恰好存在三个不同的解:

{20,48,52}, {24,45,51}, {30,40,50}

在所有的p ≤ 1000中,p取何值时有解的数目最多?


直接枚举边长a<=b<c,利用这个关系可以略微降低常数。

code

#include<bits/stdc++.h>
using namespace std;
int calc(int p)
{
    int ans=0;
    for(int a=1;a<=p/3;a++)
        for(int b=a;a+b<=p&&2*b+a<p;b++)
        //a<=b<c
        {
            int c=p-a-b;
            ans+=(a*a+b*b==c*c);
        }
    return ans;
}
int main()
{
    int n=1000,id=-1,ans=-1;
    for(int i=1;i<=n;i++)
    {
        int res=calc(i);
        if(res>ans)ans=res,id=i;
    }
    printf("%d\n",id);
    return 0;
}


Problem 40

钱珀瑙恩常数

将所有正整数连接起来构造的一个十进制无理数如下所示:

0.123456789101112131415161718192021...可以看出小数点后第12位数字是1。

如果dn表示上述无理数小数点后的第n位数字,求下式的值:

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000


考虑只讨论那些包括了要求积的数位的数字i。

那么直接调用log10搞就好了。

跑得飞快。

code

#include<bits/stdc++.h>
using namespace std;
int to[]={1,10,100,1000,10000,100000,1000000};
int top=0;
inline int len(int x)
{
    int l=0;
    while(x)l++,x/=10;
    return l;
}
inline int get(int x,int k)
{
    for(int i=1;i<=k;i++)x/=10;
    return x%10;
}
int main()
{
    int n=1000000,res=0,ans=1;
    for(int i=1;i<=n&&top<6;i++)
    {
        int k=(int)log10(i)+1;
        if(res+k<to[top]) res+=k;
        else ans*=get(i,len(i)-to[top]+res),res+=k,top++;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 41

全数字的素数

如果一个n位数恰好使用了1至n每个数字各一次,我们就称其为全数字的。例如,2143就是一个4位全数字数,同时它恰好也是一个素数。

最大的全数字的素数是多少?


发现只有n=4或n=7的时候,全数字数才可能是一个质数,其他的都是3的倍数(可以验证)

那就直接枚举n=7就好了。

另外,考虑枚举全数字数比枚举每一个数要快得多,所以我们选择枚举全排列。

再就是使用欧拉筛的效率是不高的,我们只需要判断n!个数是否是质数,n=7.

跑得飞快。

考虑到答案可能比较大,所以我们从后往前枚举全排列,找到就输出,一定最大。

跑得更快了。

code

#include<bits/stdc++.h>
using namespace std;
int a[8];
inline bool check(register int num)
{
    if(num%6!=1&&num%6!=5)return 0;
    int tmp=sqrt(num);
    for(static int i=5;i<=tmp;i+=6)
        if(num%i==0||num%(i+2)==0)
            return 0;
    return 1;
}
int main()
{
    int n=7,ans=-1;
    for(int i=1;i<=n;i++)
        a[i]=n+1-i;
    while(1)
    {
        int k=0;
        for(int i=1;i<=n;i++)
            k=(k<<3)+(k<<1)+a[i];
        if(check(k)){printf("%d\n",k);return 0;}
        prev_permutation(a+1,a+1+n);
    }
    return 0;
}


Problem 42

编码三角形数

三角形数序列的第n项由公式tn = 1/2*n(n+1)给出;因此前十个三角形数是:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...将一个单词的每个字母分别转化为其在字母表中的顺序并相加,我们可以计算出一个单词的值。例如,单词SKY的值就是 19 + 11 + 25 = 55 = t10。如果一个单词的值是一个三角形数,我们就称这个单词为三角形单词。

在这个16K的文本文件words.txt (右击并选择“目标另存为……”)中包含有将近两千个常用英文单词,这其中有多少个三角形单词?


依照题意模拟即可。

判断一个数x是否是三角形数,直接开方得k=(int)sqrt(x),如果k(k+1)==x,那就是。

code

#include<bits/stdc++.h>
using namespace std;
char a[10010];
int main()
{
    int ans=0;
    freopen("E42.txt","r",stdin);
    while(~scanf("%s",a+1))
    {
        int n=strlen(a+1),res=0;
        for(int i=1;i<=n;i++)
            res+=(a[i]-'A'+1);
        res<<=1;
        int k=sqrt(res);
        if(k*(k+1)==res)ans++;
    }
    printf("%d\n",ans);
    return 0;
}


Problem 43

子串的可整除性

1406357289是一个0至9全数字数,因为它由0到9这十个数字排列而成;但除此之外,它还有一个有趣的性质:子串的可整除性。

记d1是它的第一个数字,d2是第二个数字,依此类推,我们注意到:

  • d2d3d4=406能被2整除
  • d3d4d5=063能被3整除
  • d4d5d6=635能被5整除
  • d5d6d7=357能被7整除
  • d6d7d8=572能被11整除
  • d7d8d9=728能被13整除
  • d8d9d10=289能被17整除

找出所有满足同样性质的0至9全数字数,并求它们的和。


优雅♂地暴力枚举。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[11];
int pr[]={0,0,2,3,5,7,11,13};
int p[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
signed main()
{
    int n=10,ans=0;
    for(int i=1;i<=n;i++)
        a[i]=i-1;
    do
    {
        int res=a[2]*100+a[3]*10+a[4],f=1;
        for(int i=5;i<=10&&f;i++)
        {
            if(res%pr[i-3]!=0)f=0;
            res=(res-a[i-3]*100)*10+a[i];
        }
        if(res%17!=0)f=0;
        if(f)
            for(int i=9;i>=0;i--)
                ans+=(a[n-i]*p[i]);
    }while(next_permutation(a+1,a+1+n));
    printf("%lld\n",ans);
    return 0;
}


Problem 44

五边形数

五边形数由公式Pn=n(3n−1)/2生成。前十个五边形数是:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...可以看出P4 + P7 = 22 + 70 = 92 = P8。然而,它们的差70 − 22 = 48并不是五边形数。

在所有和差均为五边形数的五边形数对Pj和Pk中,找出使D = |Pk − Pj|最小的一对;此时D的值是多少?


暴力枚举$p_i-p_{i-1} < d$并更新答案,跑的很慢因为用了map。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int s(register int n){return n*(3*n-1)/2;}
map<int,bool> mp;
int c[2000010];
signed main()
{
    for(int i=1;i<=2000000;i++)
        c[i]=s(i),mp[c[i]]=1;
    int i=2,d=1e9+7;
    while(c[i]-c[i-1]<d)
    {
        int j=i-1;
        while(c[i]-c[j]<d&&j)
        {
            if(mp[c[i]+c[j]]&&mp[c[i]-c[j]])
                d=c[i]-c[j];
            j--;
        }
        i++;
    }
    printf("%lld\n",d);
    return 0;
}


Problem 45

三角形数、五边形数和六角形数

三角形数、五边形数和六角形数分别由以下公式给出:

三角形数Tn=n(n+1)/21, 3, 6, 10, 15, …
五边形数Pn=n(3n−1)/21, 5, 12, 22, 35, …
六边形数Hn=n(2n−1)1, 6, 15, 28, 45, …

可以验证,T285 = P165 = H143 = 40755。

找出下一个同时是三角形数、五边形数和六角形数的数。


map暴力就完了 0.2s

code

#include<bits/stdc++.h>
#define int long long
#define t(n) (n*(n+1)/2)
#define p(n) (n*(3*n-1)/2)
#define h(n) (n*(2*n-1))
using namespace std;
map<int,int> mp;
signed main()
{
    int f=0;
    for(int i=1;;i++)
    {
        int a=++mp[t(i)];
        if(p(i)<2e9)mp[p(i)]++;
        if(h(i)<2e9)mp[h(i)]++;
        if(a==3)
        {
            f++;
            if(f==2)
            {
                printf("%lld\n",t(i));
                return 0;
            }
        }
    }
    return 0;
}


Problem 46

哥德巴赫的另一个猜想

克里斯蒂安·哥德巴赫曾经猜想,每个奇合数可以写成一个素数和一个平方的两倍之和。

$9 = 7 + 2×1^2$
$15 = 7 + 2×2^2$
$21 = 3 + 2×3^2$
$25 = 7 + 2×3^2$
$27 = 19 + 2×2^2$
$33 = 31 + 2×1^2$

最终这个猜想被推翻了。

最小的不能写成一个素数和一个平方的两倍之和的奇合数是多少?


直接暴力枚举,答案很小。

code

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int st[N],pr[N],cnt;
void prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])st[i]=2,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++)
        {
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int main()
{
    prime(N-10);
    for(int i=3;;i+=2)
    {
        if(st[i]==2)continue;
        int j=0,f=1;
        while(pr[++j]<i&&j<=cnt&&f)
        {
            int del=i-pr[j];
            if(del&1)continue;
            del>>=1;int tmp=sqrt(del);
            if(tmp*tmp==del)f=0;
        }
        if(f)
        {
            printf("%d\n",i);
            return 0;
        }
    }
    return 0;
}


Problem 47

不同的质因数

首次出现连续两个数均有两个不同的质因数是在:

14 = 2 × 7

15 = 3 × 5

首次出现连续三个数均有三个不同的质因数是在:

644 = 22 × 7 × 23

645 = 3 × 5 × 43

646 = 2 × 17 × 19

首次出现连续四个数均有四个不同的质因数时,其中的第一个数是多少?


考虑暴力。

很明显连续4个数不会出现质因子种类相同的情况,所以只需要连续四个质因子数量是4的就可以了。

code

#include<bits/stdc++.h>
using namespace std;
int k[10000001];
int work(int n)
{
    int len=0;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
        {
            while(n%i==0)n/=i;
            len++;
        }
    return len+(n>1);
}
int main()
{
    for(int i=1;;i++)
    {
        k[i]=work(i);
        if(i<4)continue;
        if(k[i]==4&&k[i]==k[i-1]&&k[i]==k[i-2]&&k[i]==k[i-3])
        {
            printf("%d\n",i-3);
            return 0;
        }
    }
    return 0;
}


Problem 48

自幂

十项的自幂级数求和为 $1^1 + 2^2 + 3^3 + … + 10^{10} = 10405071317$。

求如下一千项的自幂级数求和的最后10位数字:$1^1 + 2^2 + 3^3 + … + 1000^{1000}$。


好像回到了刚开始的高精度模拟...

但确实是暴力模拟。

当我没说,最后十位直接用LongLong处理了mod 1e10.

当然,快速幂加速应该也是可行的。

code

#include<bits/stdc++.h>
using namespace std;
long long ans=0,res,p=1e10;
int main()
{
    int N=1000;
    for(int n=1;n<=N;n++)
    {
        res=1;
        for(int i=1;i<=n;i++)
            (res*=n)%=p;
        (ans+=res)%=p;
    }
    printf("%lld\n",ans);
    return 0;
}


Problem 50

连续素数的和

素数41可以写成六个连续素数的和:

41 = 2 + 3 + 5 + 7 + 11 + 13

在小于一百的素数中,41能够被写成最多的连续素数的和。

在小于一千的素数中,953能够被写成最多的连续素数的和,共包含连续21个素数。

在小于一百万的素数中,哪个素数能够被写成最多的连续素数的和?


考虑线性筛出1e7以内的质数,发现只有1e5个,那么我们就$O(n^2)$ bushi

其实理论也是$O(n^2)$的,但是我们从每个质数往后找到第一个和是质数的区间,然后这一步理论是$O(n)$的,但是我们可以在和值超过了1e7之后就break即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int st[N],pr[N],cnt;
void prime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])st[i]=2,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int main(){
    prime(N-10);
    int n=N-10;
    int ans=-1,res=-1;
    for(int i=1;i<=cnt;i++){
        int s=0,rest=-1,rans=-1;
        for(int p=i;p<=cnt&&s+pr[p]<N;p++){
            s+=pr[p];
            if(st[s]==2)rest=s,rans=p-i;
        }
        if(rans>res)res=rans,ans=rest;
    }
    printf("%d %d\n",ans,res);
    return 0;
}

最后修改:2020 年 11 月 09 日
如果觉得我的文章对你有用,请随意赞赏