Project Euler刷题记录

持续颓废更新中

(Project Euler--)一个数学题网站，以提交答案为主。

上面有一些不错的数学题，可以锻炼思维。

此篇博客用于记录(PE)上的刷题记录。

NO.1 Multiples of 3 and 5

题意：求出(sum_{i=1}^{999}i)，满足(3|i)或(5|i)。

那么暴力循环判断即可。

代码：

(Answer:233168)

#include <cstdio>

int Sum;

int main()
{
    for(int i=1;i<=999;++i)
        if(i%3==0||i%5==0)
            Sum+=i;
    printf("%dn",Sum);
    return 0;
}

NO.51 Prime digit replacements

首先筛一波素数，猜测答案不会太大，取上限(10^6)。

接着对素数暴力判断，因为要置换出(8)个素数，所以选择换的数一定(le 2)。

然后就是暴力模拟了。

(Answer:121313)

#include <cstdio>
#include <cstring>

int Ps[100005],Pn;
int Num[15],Len;//分解的数字
bool Cho[15];//是否置换
bool v[1000005];
const int Top=1000000;

bool DFS(int p,int o)
{
    if(p>Len)
    {
        int Cnt=0;
        for(int i=1;i<=Len;++i)
            if(Cho[i])
                ++Cnt;
        if(!Cnt)return false;
        Cnt=0;
        for(int i=o;i<=9;++i)
        {
            int Wn=0;
            for(int j=Len;j>=1;--j)
                if(Cho[j])Wn=Wn*10+i;
                else Wn=Wn*10+Num[j];
            if(!v[Wn])++Cnt;
        }
        return Cnt==8;
    }
    if(Num[p]==o)
    {
        Cho[p]=true;
        if(DFS(p+1,o))return true;
    }
    Cho[p]=false;
    return DFS(p+1,o);
}

bool Check(int x)
{
    Len=0;
    while(x)Num[++Len]=x%10,x/=10;
    bool Flag=true;
    for(int i=1;i<=Len;++i)
        if(Num[i]<=2)
            Flag=false;
    if(Flag)return false;
    for(int i=0;i<=2;++i)
        if(DFS(1,i))
            return true;
    return false;
}

int main()
{
    for(int i=2;i<=Top;++i)
    {
        if(!v[i])Ps[++Pn]=i;
        if(i<=Top/i)
            for(int j=i*i;j<=Top;j+=i)
                v[j]=true;
    }
    for(int i=1;i<=Pn;++i)
        if(Check(Ps[i]))
            return printf("%dn",Ps[i]),0;
}

NO.60 Prime pair sets

假设上限(10^4)。

先筛素数，预处理每两个可以连接的素数，暴搜即可。

(Answer:26033)

#include <cstdio>
#include <vector>
#include <cstring>

inline bool Prime(int x)
{
    for(int i=2;i*i<=x;++i)
        if(x%i==0)
            return false;
    return true;
}

const int Top=10000;
int Ans=0x3f3f3f3f,Cho[10];
int Ps[Top+5],Pn;
bool v[Top+5];
std::vector<int> g[Top+5];

inline bool Acon(int a,int b)
{
    int l1=1,l2=1;
    for(int i=a;i;i/=10)l1*=10;
    for(int i=b;i;i/=10)l2*=10;
    return Prime(a*l2+b)&&Prime(b*l1+a);
}

void DFS(int Cnt,int Sum)
{
    if(Sum>=Ans)return;
    if(Cnt==6)return void(Ans=Sum);
    if(Sum+Ps[Cho[Cnt-1]]>=Ans)return;
    for(int i=0;i<(int)g[Cho[Cnt-1]].size();++i)
    {
        int Next=g[Cho[Cnt-1]][i];
        bool Flag=true;
        for(int j=1;j<Cnt;++j)
            if(!Acon(Ps[Cho[j]],Ps[Next]))
                Flag=false,j=Cnt;
        if(Flag)DFS(Cnt+1,Sum+Ps[Cho[Cnt]=Next]);
    }
}

int main()
{
    for(register int i=2;i<=Top;++i)
    {
        if(!v[i])Ps[++Pn]=i;
        if(i<=Top/i)
            for(register int j=i*i;j<=Top;j+=i)
                v[j]=true;
    }
    printf("%dn",Pn);
    for(int i=1;i<=Pn;++i)
        for(int j=i+1;j<=Pn;++j)
            if(Acon(Ps[i],Ps[j]))
                g[i].push_back(j);
    for(int i=1;i<=Pn;++i)g[0].push_back(i);
    DFS(1,0);
    printf("%dn",Ans);
    return 0;
}

NO.? ?