2022-05-02发表2023-01-02更新1 小时读完 (大约9387个字)0次访问

欧拉计划完整版题解

Problem 1: Multiples of 3 and 5

（本题取 $n=1000$）

【思路】$\mathcal O(n)$ 枚举所有能被 $3$ 和被 $5$ 整除的数，最后把能被 $15$ 整除的数减掉：

#include<stdio.h>
int ans;
int main()
{
    for(int i=3;i<1000;i+=3)ans+=i;
    for(int i=5;i<1000;i+=5)ans+=i;
    for(int i=15;i<1000;i+=15)ans-=i;
    printf("%d",ans);
    return 0;
}

【优化】利用等差数列求和公式 $\mathcal O(1)$ 求解：

#include<stdio.h>
int ans;
int main()
{
    ans=((3+999)*333>>1)+((5+995)*199>>1)-((15+990)*66>>1);
    printf("%d",ans);
    return 0;
}

Problem 2: Even Fibonacci numbers

（本题取 $n=\lfloor \text{fib}^{-1}(4000000) \rfloor=33$）

【思路】运用斐波那契数列递推公式 $a_i=a_{i-1}+a_{i-2}$ 进行递推，超过 $4000000$ 就中断。最后统计其中偶数的和即可。时空复杂度均为 $\mathcal O(n)$。

【优化 $1$】采用滚动变量，将空间复杂度优化到 $\mathcal O(1)$：

#include<stdio.h>
#include<stdbool.h>
int last,now,ans;
int main()
{
    last=now=1;
    while(true)
    {
        int t=last;
        last=now;
        now+=t;
        if(now>4000000)break;
        if(now%2==0)ans+=now;
    }
    printf("%d",ans);
    return 0;
}

【优化 $2$】采用矩阵乘法，构造初始矩阵为：

$$\begin{bmatrix}
1 & 1 \cr
0 & 0 \cr
\end{bmatrix}$$

每次需要乘上的矩阵为：

$$\begin{bmatrix}
1 & 1 \cr
1 & 0 \cr
\end{bmatrix}$$

这样不停地累乘，只要矩阵第 $1$ 行第 $1$ 列的元素（即数列的值）超过 $4000000$，就直接中断：

#include<bits/stdc++.h>
int ans;
struct matrix
{
    long long a[3][3];
    matrix operator*(const matrix &x)const
    {
        matrix res;
        memset(res.a,0,sizeof(res.a));
        for(int k=1;k<=2;++k)
        {
            for(int i=1;i<=2;++i)
            {
                for(int j=1;j<=2;++j)
                {
                    res.a[i][j]+=a[i][k]*x.a[k][j];
                }
            }
        }
        return res;
    }
}m,base;
int main()
{
    m.a[1][1]=m.a[1][2]=1;
    base.a[1][1]=base.a[1][2]=base.a[2][1]=1;
    while(m.a[1][1]<=4000000)
    {
        if(m.a[1][1]%2==0)ans+=m.a[1][1];
        m=m*base;
    }
    printf("%d",ans);
    return 0;
}

做一次矩阵乘法的时间复杂度为 $\mathcal O(1)$，需要做 $n$ 次，因此时间复杂度仍为 $\mathcal O(n)$。矩阵的大小为常数，因此空间复杂度为 $\mathcal O(1)$。

由于没有要求具体求出数列中一个元素的值，因此矩阵并没有真正起到优化作用。

Problem 3: Largest prime factor

（本题取 $n=600851475143$）

【思路】在区间 $[2,n]$ 内倒序枚举 $n$ 的所有质因数，输出第一个遍历到的。时空复杂度分别为 $\mathcal O(n \sqrt n)$，$\mathcal O(1)$。

【优化 $1$】在原思路的基础上使用埃氏筛，时间复杂度优化为 $\mathcal O(n \ln \ln n+n)$；使用欧拉筛可优化为 $\mathcal O(n)$。

【优化 $2$】在原思路的基础上将区间缩小为 $[2,\sqrt n]$，时间复杂度优化为 $\mathcal O(n)$。

【优化 $3$】结合优化 $1,2$，时间复杂度可进一步优化至 $\mathcal O(\sqrt n)$（后面研究质数时不再提及质数判断法或埃氏筛，一律只保留欧拉筛）。

【优化 $4$】在【优化 $3$】的基础上，将循环改为正序。这样能减小时间复杂度的常数，同时将空间复杂度降为 $\mathcal O(1)$：

#include<stdio.h>
long long n=600851475143;
int main()
{
    for(long long i=3;i*i<=n;i+=2)
    {
        while(n%i==0)
        {
            n/=i;
            if(n==1)
            {
                printf("%lld",i);
                return 0;
            }
        }
    }
    printf("%lld",n);
    return 0;
}

Problem 4: Largest palindrome product

（本题取 $d=10$，$n=1000-100=900$）

【思路】显然满足要求的最大回文数一定为六位数。因此我们只需要三重循环枚举前三位，然后通过回文数性质得到后三位，从而得到一个六位数。最后枚举是否能表示成两个三位数乘积即可。时间复杂度为 $\mathcal O(d^3n)$：

#include<stdio.h>
int main()
{
    for(int i=9;i;--i)
    {
        for(int j=9;j>=0;--j)
        {
            for(int k=9;k>=0;--k)
            {
                int x=i*100000+j*10000+k*1000+k*100+j*10+i;
                for(int p=100;p<=999;++p)
                {
                    if(x%p)continue;
                    int q=x/p;
                    if(q>=100&&q<1000)
                    {
                        printf("%d",x);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

Problem 5: Smallest multiple

（本题取 $n=20$）

【思路】本题只需求 $1 \sim 20$ 的最小公倍数即可。

而 $\text{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}$，因此问题转化成了求 $\gcd$（为了防止爆 int 可以先除后乘或者直接开 long long）。时间复杂度为 $\mathcal O(\log n)$：

#include<stdio.h>
int ans=1;
int gcd(int a,int b)
{
    while(b)
    {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int main()
{
    for(int i=1;i<=20;++i)ans=lcm(ans,i);
    printf("%d",ans);
    return 0;
}

Problem 6: Sum square difference

（本题取 $n=100$）

【思路】先求平方的和，再求和的平方，最后相减。时间复杂度为 $\mathcal O(n)$：

#include<stdio.h>
int sum;
int square(int x){return x*x;}
int main()
{
    for(int i=1;i<=100;++i)sum+=square(i);
    printf("%d",square((1+100)*100>>1)-sum);
    return 0;
}

Problem 7: 10001st prime

（本题取 $n=\text{prime}_{10001}=104743$）

【思路】使用 $\mathcal O(n)$ 的欧拉筛：

#include<stdio.h>
#include<stdbool.h>
const int maxn=200000;
int prime[maxn];
bool vis[maxn];
int euler(int x)
{
    for(int i=2;i<=maxn&&prime[0]<x;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0]&&prime[0]<x;++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
    return prime[x];
}
int main()
{
    printf("%d",euler(10001));
    return 0;
}

Problem 8: Largest product in a series

（本题取 $n=1000$，m=13$）

【思路】$\mathcal O(nm)$ 暴力枚举：

#include<stdio.h>
const char *s="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
long long ans;
int main()
{
    for(int i=0;i<988;++i)
    {
        long long x=1;
        for(int j=i;j<i+13;++j)x*=(s[j]^48);
        if(x>ans)ans=x;
    }
    printf("%lld",ans);
    return 0;
}

Problem 9: Special Pythagorean triplet

（本题取 $n=1000$）

【思路】$\mathcal O(n^3)$ 分别枚举 $a,b,c$ 并判断。

【优化】由于 $a,b,c$ 中的其中一个值可以由另外两个得到，因此可省去第三重循环，时间复杂度优化为 $\mathcal O(n^2)$：

#include<stdio.h>
int main()
{
    for(int a=0;a<1000;++a)
    {
        for(int b=a+1;b<1000;++b)
        {
            int c=1000-a-b;
            if(b<c&&a*a+b*b==c*c)
            {
                printf("%d",a*b*c);
                return 0;
            }
        }
    }
    return 0;
}

Problem 10: Summation of primes

（本题取 $n=2000000$）

【思路】$\mathcal O(n)$ 欧拉筛：

#include<stdio.h>
#include<stdbool.h>
const int maxn=2000000;
int prime[maxn];
bool vis[maxn];
long long ans;
void euler()
{
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])
        {
            prime[++prime[0]]=i;
            ans+=i;
        }
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    euler();
    printf("%lld\n",ans);
    return 0;
}

Problem 11: Largest product in a grid

（本题取 $n=20$，$m=4$，$d=8$）

【思路】先 $O(n^2)$ 枚举起始数字，然后 $\mathcal O(md)$ 枚举所有方向的所有数字。时间复杂度为 $\mathcal O(n^2md)$：

#include<stdio.h>
const int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
int ans;
const int matrix[20][20]=
{
    {8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,8},
    {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},
    {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},
    {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},
    {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
    {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},
    {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
    {67,26,20,68,02,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21},
    {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
    {21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},
    {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,9,53,56,92},
    {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},
    {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},
    {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},
    {04,52,8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},
    {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},
    {04,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36},
    {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},
    {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},
    {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}
};
int main()
{
    for(int i=0;i<20;++i)
    {
        for(int j=0;j<20;++j)
        {
            for(int k=0;k<8;++k)
            {
                int mx=i+dx[k]*3,my=j+dy[k]*3,fac=matrix[i][j];
                if(mx<0||my<0||mx>=20||my>=20)continue;
                for(int l=0,lx=i,ly=j;l<3;++l)
                {
                    int nx=lx+dx[k],ny=ly+dy[k];
                    fac*=matrix[nx][ny];
                    lx=nx,ly=ny;
                }
                if(fac>ans)ans=fac;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 12: Highly divisible triangular number

（本题取 $n$ 为第一个因数个数大于 $500$ 的三角形数 $76576500$）

【思路】依次枚举三角形数，每次 $\mathcal O(n)$ 求所有因数，因数个数大于 $500$ 就中断。时间复杂度为 $\mathcal O(n^2)$。

【优化】如果整数 $x$ 有因数 $i$，那么 $\dfrac{x}{i}$ 必然也是它的因数。因此可以把统计因数个数的时间复杂度降到 $\mathcal O(\sqrt n)$，总体优化到 $\mathcal O(n \sqrt n)$：

#include<stdio.h>
int fac(int x)
{
    if(x==1)return 1;
    int s=2;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            ++s;
            if(i*i!=x)++s;
        }
    }
    return s;
}
int main()
{
    for(int i=1,x=1;;++i,x+=i)
    {
        if(fac(x)>500)
        {
            printf("%d",x);
            return 0;
        }
    }
    return 0;
}

Problem 13: Large sum

【思路】C/C++ 应用高精度，但 Python 可直接计算。同时还可以利用整型和字符串之间的转换和子串功能求解：

a = [
    37107287533902102798797998220837590246510135740250,
    46376937677490009712648124896970078050417018260538,
    74324986199524741059474233309513058123726617309629,
    91942213363574161572522430563301811072406154908250,
    23067588207539346171171980310421047513778063246676,
    89261670696623633820136378418383684178734361726757,
    28112879812849979408065481931592621691275889832738,
    44274228917432520321923589422876796487670272189318,
    47451445736001306439091167216856844588711603153276,
    70386486105843025439939619828917593665686757934951,
    62176457141856560629502157223196586755079324193331,
    64906352462741904929101432445813822663347944758178,
    92575867718337217661963751590579239728245598838407,
    58203565325359399008402633568948830189458628227828,
    80181199384826282014278194139940567587151170094390,
    35398664372827112653829987240784473053190104293586,
    86515506006295864861532075273371959191420517255829,
    71693888707715466499115593487603532921714970056938,
    54370070576826684624621495650076471787294438377604,
    53282654108756828443191190634694037855217779295145,
    36123272525000296071075082563815656710885258350721,
    45876576172410976447339110607218265236877223636045,
    17423706905851860660448207621209813287860733969412,
    81142660418086830619328460811191061556940512689692,
    51934325451728388641918047049293215058642563049483,
    62467221648435076201727918039944693004732956340691,
    15732444386908125794514089057706229429197107928209,
    55037687525678773091862540744969844508330393682126,
    18336384825330154686196124348767681297534375946515,
    80386287592878490201521685554828717201219257766954,
    78182833757993103614740356856449095527097864797581,
    16726320100436897842553539920931837441497806860984,
    48403098129077791799088218795327364475675590848030,
    87086987551392711854517078544161852424320693150332,
    59959406895756536782107074926966537676326235447210,
    69793950679652694742597709739166693763042633987085,
    41052684708299085211399427365734116182760315001271,
    65378607361501080857009149939512557028198746004375,
    35829035317434717326932123578154982629742552737307,
    94953759765105305946966067683156574377167401875275,
    88902802571733229619176668713819931811048770190271,
    25267680276078003013678680992525463401061632866526,
    36270218540497705585629946580636237993140746255962,
    24074486908231174977792365466257246923322810917141,
    91430288197103288597806669760892938638285025333403,
    34413065578016127815921815005561868836468420090470,
    23053081172816430487623791969842487255036638784583,
    11487696932154902810424020138335124462181441773470,
    63783299490636259666498587618221225225512486764533,
    67720186971698544312419572409913959008952310058822,
    95548255300263520781532296796249481641953868218774,
    76085327132285723110424803456124867697064507995236,
    37774242535411291684276865538926205024910326572967,
    23701913275725675285653248258265463092207058596522,
    29798860272258331913126375147341994889534765745501,
    18495701454879288984856827726077713721403798879715,
    38298203783031473527721580348144513491373226651381,
    34829543829199918180278916522431027392251122869539,
    40957953066405232632538044100059654939159879593635,
    29746152185502371307642255121183693803580388584903,
    41698116222072977186158236678424689157993532961922,
    62467957194401269043877107275048102390895523597457,
    23189706772547915061505504953922979530901129967519,
    86188088225875314529584099251203829009407770775672,
    11306739708304724483816533873502340845647058077308,
    82959174767140363198008187129011875491310547126581,
    97623331044818386269515456334926366572897563400500,
    42846280183517070527831839425882145521227251250327,
    55121603546981200581762165212827652751691296897789,
    32238195734329339946437501907836945765883352399886,
    75506164965184775180738168837861091527357929701337,
    62177842752192623401942399639168044983993173312731,
    32924185707147349566916674687634660915035914677504,
    99518671430235219628894890102423325116913619626622,
    73267460800591547471830798392868535206946944540724,
    76841822524674417161514036427982273348055556214818,
    97142617910342598647204516893989422179826088076852,
    87783646182799346313767754307809363333018982642090,
    10848802521674670883215120185883543223812876952786,
    71329612474782464538636993009049310363619763878039,
    62184073572399794223406235393808339651327408011116,
    66627891981488087797941876876144230030984490851411,
    60661826293682836764744779239180335110989069790714,
    85786944089552990653640447425576083659976645795096,
    66024396409905389607120198219976047599490197230297,
    64913982680032973156037120041377903785566085089252,
    16730939319872750275468906903707539413042652315011,
    94809377245048795150954100921645863754710598436791,
    78639167021187492431995700641917969777599028300699,
    15368713711936614952811305876380278410754449733078,
    40789923115535562561142322423255033685442488917353,
    44889911501440648020369068063960672322193204149535,
    41503128880339536053299340368006977710650566631954,
    81234880673210146739058568557934581403627822703280,
    82616570773948327592232845941706525094512325230608,
    22918802058777319719839450180888072429661980811197,
    77158542502016545090413245809786882778948721859617,
    72107838435069186155435662884062257473692284509516,
    20849603980134001723930671666823555245252804609722,
    53503534226472524250874054075591789781264330331690
]
s = 0
for i in range(100):
    s += a[i]
ans = str(s)[0: 10]
print(ans)

Problem 14: Longest Collatz sequence

（本题取 $n=1000000$，规定 $\text{col}_n$ 为 $n$ 的序列长度）

【思路】直接 $\mathcal O(n \max {\text{col}_i})$ 求解：

#include<stdio.h>
int ans,maxn;
int main()
{
    for(int i=1;i<=1000000;++i)
    {
        int x=1;
        long long t=i;
        while(t!=1)
        {
            if(t&1)t=t*3+1;
            else t>>=1;
            ++x;
        }
        if(x>maxn)
        {
            ans=i;
            maxn=x;
        }
    }
    printf("%d",ans);
    return 0;
}

【优化】采用记忆化减小常数：

#include<stdio.h>
int ans,f[1000001];
int main()
{
    for(int i=1;i<=1000000;++i)
    {
        if(!f[i])
        {
            f[i]=1;
            long long t=i;
            int a[1001]={};
            while(t!=1)
            {
                if(t&1)t=t*3+1;
                else t>>=1;
                ++f[i];
                if(t<=1000000)
                {
                    a[f[i]]=t;
                    if(f[t])
                    {
                        f[i]+=f[t]-1;
                        break;
                    }
                }
            }
            for(int j=2;j<=f[i];++j)
            {
                if(a[j])
                {
                    f[a[j]]=f[i]-j+1;
                }
            }
        }
        if(f[i]>f[ans])ans=i;
    }
    printf("%d",ans);
    return 0;
}

Problem 15: Lattice paths

（本题取 $n=20$）

【思路】$\mathcal O(n^2)$ DP 即可：

#include<stdio.h>
long long f[21][21];
int main()
{
    for(int i=0;i<=20;++i)f[0][i]=f[i][0]=1;
    for(int i=1;i<=20;++i)
    {
        for(int j=1;j<=20;++j)
        {
            f[i][j]=f[i][j-1]+f[i-1][j];
        }
    }
    printf("%lld",f[20][20]);
    return 0;
}

Problem 16: Power digit sum

【思路】Python 可简单模拟，但在 C/C++ 中需用高精度：

s = str(1 << 1000)
ans = 0
for i in s:
    ans += int(i)
print(ans)

Problem 17: Number letter counts

（本题取 $n=1000$）

【思路】本题细节较多，可先预处理一些数的字母个数，这样后面的数就可以由前面递推而来。时间复杂度为 $\mathcal O(n)$。

#include<stdio.h>
int ans,a[1001]={0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8};
void init()
{
    a[20]=a[30]=6;
    a[40]=a[50]=a[60]=5;
    a[70]=7;
    a[80]=a[90]=6;
    a[1000]=11;
    for(int i=20;i<100;++i)
    {
        if(i%10==0)continue;
        a[i]=a[i/10*10]+a[i%10];
    }
}
int main()
{
    init();
    for(int i=1;i<=1000;++i)
    {
        if(a[i])ans+=a[i];
        else if(i%100)ans+=a[i/100]+10+a[i%100];
        else ans+=a[i/100]+7;
    }
    printf("%d",ans);
    return 0;
}

Problem 18: Maximum path sum I

（本题取 $n=16$）

【思路】暴力 DFS，时间复杂度为 $\mathcal O(2^n)$。

【优化】采用 $\mathcal O(n^2)$ 的 DP：

#include<stdio.h>
int dp[16][16],ans;
int max(int a,int b){return a>b?a:b;}
const int matrix[16][16]=
{
    {0},
    {0,75},
    {0,95,64},
    {0,17,47,82},
    {0,18,35,87,10},
    {0,20,04,82,47,65},
    {0,19,01,23,75,03,34},
    {0,88,02,77,73,07,63,67},
    {0,99,65,04,28,06,16,70,92},
    {0,41,41,26,56,83,40,80,70,33},
    {0,41,48,72,33,47,32,37,16,94,29},
    {0,53,71,44,65,25,43,91,52,97,51,14},
    {0,70,11,33,28,77,73,17,78,39,68,17,57},
    {0,91,71,52,38,17,14,91,43,58,50,27,29,48},
    {0,63,66,04,68,89,53,67,30,73,16,69,87,40,31},
    {0,04,62,98,27,23,9,70,98,73,93,38,53,60,04,23}
};
int main()
{
    for(int i=1;i<=15;++i)
    {
        for(int j=1;j<=i;++j)
        {
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+matrix[i][j];
        }
    }
    for(int i=1;i<=15;++i)ans=max(ans,dp[15][i]);
    printf("%d",ans);
    return 0;
}

Problem 19: Counting Sundays

【思路】按照题意模拟即可：

#include<stdio.h>
#include<stdbool.h>
const int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans,d=1;
int main()
{
    for(int m=1;m<=12;++m)d=(d+days[m])%7;
    for(int y=1901;y<=2000;++y)
    {
        for(int m=1;m<=12;++m)
        {
            if(!d)++ans;
            d=(d+days[m]+(m==2&&((bool)(y&3)^true)))%7;
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 20: Factorial digit sum

【思路】Python 模拟 / C/C++ 高精度：

import math
s = str(math.factorial(100))
ans = 0
for i in s:
    ans += int(i)
print(ans)

Problem 21: Amicable numbers

（本题取 $n=10000$）

【思路】先 $\mathcal O(n)$ 预处理 $1 \sim 10000$ 因数个数，然后 $\mathcal O(n)$ 枚举，总体时间复杂度仍为 $\mathcal O(n)$：

#include<stdio.h>
int ans,d[10001];
int main()
{
    for(int i=1;i<=10000;++i)
    {
        for(int j=i<<1;j<=10000;j+=i)
        {
            d[j]+=i;
        }
    }
    for(int i=1;i<=10000;++i)
    {
        if(d[i]<=10000&&d[d[i]]==i&&d[i]!=i)
        {
            ans+=i;
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 22: Names scores

【思路】从文件读入所有名字，然后模拟。难点在于读入的方法。当然也可以另编写一个程序，将所有名字每几个就换一次行，然后把表存在最终程序里（详见 Problem 42）：

#include<bits/stdc++.h>
using namespace std;
string s[6001],t;
int n,ans;
bool read(string &s)
{
    char ch=getchar();
    if(ch==EOF)return false;
    while(ch<'A'||ch>'Z')
    {
        ch=getchar();
        if(ch==EOF)return false;
    }
    s=ch;
    while(true)
    {
        ch=getchar();
        if(ch<'A'||ch>'Z')break;
        s+=ch;
    }
    return true;
}
int main()
{
    freopen("p022_names.txt","r",stdin);
    while(read(t))s[++n]=t;
    sort(s+1,s+n+1);
    for(int i=1;i<=n;++i)
    {
        int x=0;
        for(int j=0;s[i][j];++j)x+=s[i][j]-'A'+1;
        ans+=x*i;
    }
    printf("%d",ans);
    return 0;
}

Problem 23: Non-abundant sums

（本题取 $n=28123$）

【思路】$\mathcal O(n \sqrt n)$ 预处理因数个数（用 Problem 21 的思路可优化至 $\mathcal O(n)$），然后 $\mathcal O(n^2)$ 模拟。最终的时间复杂度都为 $\mathcal O(n^2)$：

#include<stdio.h>
#include<stdbool.h>
int ans;
bool a[30001];
int fac(int x)
{
    if(x==1)return 1;
    int s=1;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            s+=i;
            if(i*i!=x)s+=x/i;
        }
    }
    return s;
}
int main()
{
    for(int i=1;i<=28123;++i)a[i]=fac(i)>i;
    for(int i=1;i<=28123;++i)
    {
        bool flag=false;
        for(int j=1;j<=i>>1;++j)
        {
            if(a[j]&a[i-j])
            {
                flag=true;
                break;
            }
        }
        if(!flag)ans+=i;
    }
    printf("%d",ans);
    return 0;
}

Problem 24: Lexicographic permutations

（本题取 $n=10$）

【思路】$\mathcal O(n!)$ 枚举所有排列情况，可用 DFS 实现或直接调用函数 next_permutation：

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
int a[10],cnt;
bool b[10];
void dfs(int k)
{
    if(k>9)
    {
        if(++cnt==1000000)
        {
            for(int i=0;i<10;++i)printf("%d",a[i]);
            exit(0);
        }
        return;
    }
    for(int i=0;i<10;++i)
    {
        if(b[i])continue;
        a[k]=i;
        b[i]=true;
        dfs(k+1);
        b[i]=false;
    }
}
int main()
{
    dfs(0);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int cnt,a[10];
int main()
{
    for(int i=0;i<=9;++i)a[i]=i;
    while(next_permutation(a,a+10)&&++cnt<999999);
    for(int i=0;i<=9;++i)printf("%d",a[i]);
    return 0;
}

Problem 25: 1000-digit Fibonacci number

【思路】采用 Problem 2 中滚动数组的方法，再使用 Python 模拟 / C/C++ 高精度：

import sys
a = b = 1
ans = 2
while True:
    a, b = b, a + b
    ans += 1
    if len(str(b)) == 1000:
        print(ans)
        sys.exit()

Problem 26: Reciprocal cycles

【思路】这题的关键就是如何得到循环节。试想，当我们把一个单位分数扩大 $10$ 的若干次幂之后，得到的数的整数部分会出现循环。

因此，我们可以重复地将一个初始值为 $1$ 的数对单位分数的分母取模，然后乘上 $10$。

每操作一次，就检查这个数是否已经出现过。如果出现过，就说明已经找到循环节；否则标记并继续操作：

#include<stdio.h>
#include<stdbool.h>
#include<string.h>
int ans,maxn;
bool vis[10001];
int main()
{
    for(int i=3;i<1000;i+=2)
    {
        int r=1,cur=0;
        memset(vis,false,sizeof(vis));
        while(!vis[r])
        {
            vis[r]=true;
            r=r%i*10;
            ++cur;
        }
        if(cur>maxn)
        {
            ans=i;
            maxn=cur;
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 27: Quadratic primes

（本题取 $n=1000$）

【思路】由于范围不大，因而可以直接 $\mathcal O(n^2)$ 枚举，然后套上质数的判断即可。由于待判断的数大小不确定，因而用质数判断函数来代替欧拉筛：

#include<stdio.h>
#include<stdbool.h>
int maxn,ans;
bool prime(int x)
{
    if(x<2)return false;
    if(x==2||x==3||x==5)return true;
    if(x%2==0||x%3==0||x%5==0)return false;
    for(int a=7,b=11;a*a<=x;a+=6,b+=6)if(x%a==0||x%b==0)return false;
    return true;
}
int main()
{
    for(int a=-999;a<=999;++a)
    {
        for(int b=-1000;b<=1000;++b)
        {
            int n=0;
            while(prime(n*n+a*n+b))++n;
            if(n>maxn)
            {
                maxn=n;
                ans=a*b;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 28: Number spiral diagonals

（本题取 $n=1000$）

【思路】首先可以发现 $1$ 位于矩阵正中央，即 $(501,501)$ 处。

通过找规律可以发现，每走一步需要顺时针变换一次方向，但是如果已经走过或越界则需再次变换。这样，我们就可以遍历整个矩阵，从而在 $\mathcal O(n^2)$ 的效率下求出对角线的元素之和：

#include<stdio.h>
int x=501,y=501,cnt,d=-1,ans,a[1005][1005];
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int main()
{
    while(cnt<=1002001)
    {
        a[x][y]=++cnt;
        d=(d+1)%4;
        int nx=x+dx[d],ny=y+dy[d];
        if(nx<1||ny<1||nx>1001||ny>1001||a[nx][ny])
        {
            d=(d+3)%4;
            x+=dx[d],y+=dy[d];
        }
        else x=nx,y=ny;
    }
    for(int i=1;i<=1001;++i)ans+=a[i][i]+a[i][1002-i];
    printf("%d",ans-1);
    return 0;
}

Problem 29: Distinct powers

（本题取 $n=100$）

【思路】考虑构造一个元素不可重的集合，通过 $\mathcal O(n^2)$ 的二维循环枚举所有乘方的结果，最后统计集合内元素个数：

a = []
for i in range(2, 101):
    for j in range(2, 101):
        a.append(i ** j)
print(len(list(set(a))))

Problem 30: Digit fifth powers

【思路】从二位数开始枚举，直到到达一个较大的预先设置好的上界，在枚举时暴力判断是否符合题意即可：

#include<stdio.h>
int ans;
int pow5(int x){return x*x*x*x*x;}
int main()
{
    for(int i=11;i<=500000;++i)
    {
        int j=i,t=0;
        while(j)
        {
            t+=pow5(j%10);
            j/=10;
        }
        if(i==t)ans+=i;
    }
    printf("%d",ans);
    return 0;
}

Problem 31: Coin sums

（本题取 $n=200$，$m=8$）

【思路】通过观察不难发现本题考察的是 DP。

如果我们用 $dp_{i,j}$ 表示使用 $j$ 种不同面额凑出 $i$ 分钱的方案个数，那么显然有初始状态：

$$dp_{0,1}=1$$

由于本题数据范围不大，我们可以暴力递推，从而覆盖所有情况。用 $val_i$ 表示第 $i$ 种货币的面额，则有：

$$dp_{i,j}=\sum_{i=1}^n \sum_{j=1}^m \sum_{k=1}^j dp_{i-val_j,k}$$

这样我们便得到了一个 $\mathcal O(nm^2)$ 的做法：

#include<stdio.h>
const int value[]={0,1,2,5,10,20,50,100,200};
int dp[201][10],ans;
int main()
{
    dp[0][1]=1;
    for(int i=1;i<=200;++i)
    {
        for(int j=1;value[j]<=i;++j)
        {
            for(int k=1;k<=j;++k)
            {
                dp[i][j]+=dp[i-value[j]][k];
            }
        }
    }
    for(int i=1;i<10;++i)ans+=dp[200][i];
    printf("%d",ans);
    return 0;
}

【优化】我们可以采用完全背包进行优化。

不妨用 $dp_j$ 表示能够凑出 $j$ 分钱的方案总数，则初始状态为：

$$dp_0=1$$

接着我们使用完全背包的递推方式：

$$dp_j=\sum_{i=1}^m \sum_{j=val_i}^n dp_{j-val_i}$$

这样我们可以将时间复杂度优化到 $\mathcal O(nm)$，空间复杂度优化到 $\mathcal O(n)$：

#include<stdio.h>
const int value[]={0,1,2,5,10,20,50,100,200};
int dp[201],ans;
int main()
{
    dp[0]=1;
    for(int i=1;i<=8;++i)
    {
        for(int j=value[i];j<=200;++j)
        {
            dp[j]+=dp[j-value[i]];
        }
    }
    printf("%d",dp[200]);
    return 0;
}

Problem 32: Pandigital products

（本题取 $n=9$）

【思路】我们可以 $\mathcal O(n!)$ 获得 $1 \sim 9$ 的排列，然后在排列组成的九位数中插两个空——其中一个位于两个乘数之间（相当于乘号），另一个位于左式和右式之间（相当于等号）。最后我们检查一下等式是否正确，正确就累加进入答案：

#include<stdio.h>
#include<stdbool.h>
int ans,a[10];
bool vis[10],flag[10000];
void dfs(int k)
{
    if(k>9)
    {
        for(int i=1;i<=2;++i)
        {
            int m1=0;
            for(int j=1;j<=i;++j)m1=m1*10+a[j];
            for(int j=i;j<=5-i;++j)
            {
                int m2=0,p=0;
                for(int k=i+1;k<=i+j;++k)m2=m2*10+a[k];
                for(int k=i+j+1;k<=9;++k)p=p*10+a[k];
                if(m1*m2==p&&!flag[p])
                {
                    flag[p]=true;
                    ans+=p;
                }
            }
        }
        return;
    }
    for(int i=1;i<=9;++i)
    {
        if(vis[i])continue;
        a[k]=i;
        vis[i]=true;
        dfs(k+1);
        vis[i]=false;
    }
}
int main()
{
    dfs(1);
    printf("%d",ans);
    return 0;
}

Problem 33: Digit cancelling fractions

（本题取 $n=9$）

【思路】题目描述得有些模糊，要求我们找到两个十位数 $a,b$（$a \lt b$），使得 $a$ 的十位数和 $b$ 的个位数相等，同时使得 $\dfrac{a}{b}$ 与 $a,b$ 分别删去相同位数之后的商相等。

由于有两个数位相等，因此我们只需要枚举三个数位，这样就可以在 $\mathcal O(n^3)$ 枚举出所有的情况。约分需要用到 $\gcd$，因此最终时间复杂度为 $\mathcal O(n^3 \log n)$：

#include<stdio.h>
struct fraction
{
    int n,d;
}ans;
int gcd(int a,int b)
{
    while(b)
    {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int main()
{
    ans.n=ans.d=1;
    for(int i=1;i<=9;++i)
    {
        for(int j=i+1;j<=9;++j)
        {
            for(int k=i+1;k<=9;++k)
            {
                int n=i*10+j,d=j*10+k;
                if(n*k==d*i)
                {
                    ans.n*=n;
                    ans.d*=d;
                }
            }
        }
    }
    printf("%d",ans.d/gcd(ans.n,ans.d));
    return 0;
}

Problem 34: Digit factorials

（本题取 $n=9$）

【思路】我们可以储存 $0 \sim 9$ 的所有阶乘的值，然后在 $[10,9!]$ 内枚举所有的数并检验即可。枚举的时间复杂度为 $\mathcal O(n!)$：

#include<stdio.h>
const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int ans;
int main()
{
    for(int i=10;i<=362880;++i)
    {
        int j=i,s=0;
        while(j)
        {
            s+=fac[j%10];
            j/=10;
        }
        if(s==i)ans+=i;
    }
    printf("%d",ans);
    return 0;
}

Problem 35: Circular primes

（本题取 $n=1000000$）

【思路】先 $\mathcal O(n)$ 欧拉筛，然后暴力枚举所有在范围内的质数：

#include<stdio.h>
#include<math.h>
#include<stdbool.h>
const int maxn=1000000;
int ans,a[7],prime[maxn];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    euler();
    for(int i=1;i<=prime[0];++i)
    {
        int x=prime[i],y=x,n=log10(x)+1;
        bool f=true;
        for(int j=1;j<=n;++j)
        {
            a[n-j+1]=y%10;
            y/=10;
        }
        for(int j=2;j<=n;++j)
        {
            int z=0;
            for(int k=1;k<=n;++k)
            {
                int pos=j+k-1;
                if(pos>n)pos-=n;
                z=z*10+a[pos];
            }
            if(vis[z])
            {
                f=false;
                break;
            }
        }
        ans+=f;
    }
    printf("%d",ans);
    return 0;
}

Problem 36: Double-base palindromes

（本题取 $n=1000000$）

【思路】我们可以 $\mathcal O(n)$ 枚举所有在范围的整数，然后每次 $\mathcal O(\log n)$ 进行数位的处理和检查。总体时间复杂度为 $\mathcal O(n \log n)$：

#include<stdio.h>
#include<stdbool.h>
int ans,d[7],b[21];
int main()
{
    for(int i=1;i<1000000;++i)
    {
        int j=i,cd=0,cb=0;
        bool flag=true;
        while(j)
        {
            d[++cd]=j%10;
            j/=10;
        }
        for(int k=1;k<=cd>>1;++k)
        {
            if(d[k]!=d[cd-k+1])
            {
                flag=false;
                break;
            }
        }
        if(!flag)continue;
        j=i;
        while(j)
        {
            b[++cb]=j&1;
            j>>=1;
        }
        for(int k=1;k<=cb>>1;++k)
        {
            if(b[k]!=b[cb-k+1])
            {
                flag=false;
                break;
            }
        }
        if(flag)ans+=i;
    }
    printf("%d",ans);
    return 0;
}

Problem 37: Truncatable primes

（本题取 $n=1000000$）

【思路】$\mathcal O(n)$ 欧拉筛，然后枚举所有在范围内质数并检查是否符合题意。程序的时间复杂度为 $\mathcal O(n \log_{10} n)$：

#include<stdio.h>
#include<stdbool.h>
#include<math.h>
const int maxn=1000000;
const int pow10[]={1,10,100,1000,10000,100000,1000000};
int ans,prime[maxn];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    euler();
    for(int i=5;i<=prime[0];++i)
    {
        int x=prime[i],y=x;
        if(vis[x])continue;
        bool flag=true;
        while(true)
        {
            y/=10;
            if(!y)break;
            if(vis[y])
            {
                flag=false;
                break;
            }
        }
        y=x;
        while(y)
        {
            if(y<10)break;
            y%=pow10[int(log10(y))];
            if(vis[y])
            {
                flag=false;
                break;
            }
        }
        if(flag)ans+=x;
    }
    printf("%d",ans);
    return 0;
}

Problem 38: Pandigital multiples

【思路】暴力倒序枚举 $10000$ 以内的整数并检查：

#include<stdio.h>
#include<stdbool.h>
int main()
{
    for(int i=9999;i;--i)
    {
        for(int j=2;;++j)
        {
            int a[10]={},b[10]={};
            for(int k=1;k<=j;++k)
            {
                int x=i*k;
                b[k]=x;
                while(x)
                {
                    ++a[x%10];
                    x/=10;
                }
            }
            bool flag=true;
            int cnt=a[0];
            for(int k=1;k<10;++k)
            {
                cnt+=a[k];
                if(a[k]!=1)flag=false;
            }
            if(cnt>9)break;
            if(flag)
            {
                for(int k=1;k<=j;++k)printf("%d",b[k]);
                return 0;
            }
        }
    }
    return 0;
}

Problem 39: Integer right triangles

（本题取 $n=1000$）

【思路】最外层枚举 $p$ 的值，里面两层枚举 $a,b$，从而计算得到是否有符合的 $c$。时间复杂度为 $\mathcal O(n^3)$：

#include<stdio.h>
int maxp,maxn;
int main()
{
    for(int p=12;p<=1000;++p)
    {
        int s=0;
        for(int a=3;a<=p/3;++a)
        {
            for(int b=a+1;b<=p;++b)
            {
                int c=p-a-b;
                if(a*a+b*b==c*c&&c>b)++s;
            }
        }
        if(s>maxn)
        {
            maxn=s;
            maxp=p;
        }
    }
    printf("%d",maxp);
    return 0;
}

Problem 40: Champernowne’s constant

【思路】由于一个整数 $x$ 的数位个数等于 $\log_{10} x+1$，因而我们可以不停累加，到了所需的值就进行计算：

#include<stdio.h>
#include<math.h>
const int a[]={1,10,100,1000,10000,100000,1000000};
int cnt,ans=1;
int main()
{
    for(int i=1,x=0;x<=1000000;++i)
    {
        int len=log10(i)+1,j=i;
        x+=len;
        if(x>=a[cnt])
        {
            for(int k=0;k<x-a[cnt];++k)j/=10;
            ans*=j%10;
            ++cnt;
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 41: Pandigital prime

（本题取 $n=9$）

【思路】$\mathcal O(n!)$ 构造全排列并判断是否为质数。由于 $n$ 较大，因此不宜使用欧拉筛。程序的时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$：

#include<stdio.h>
#include<stdbool.h>
#include<string.h>
int ans,a[10];
bool vis[10];
bool prime(int x)
{
    if(x<2)return false;
    if(x==2||x==3||x==5)return true;
    if(x%2==0||x%3==0||x%5==0)return false;
    for(int a=7,b=11;a*a<=x;a+=6,b+=6)if(x%a==0||x%b==0)return false;
    return true;
}
void dfs(int k,int n)
{
    if(k>n)
    {
        int x=0;
        for(int i=1;i<=n;++i)x=x*10+a[i];
        if(prime(x)&&x>ans)ans=x;
        return;
    }
    for(int i=1;i<=n;++i)
    {
        if(vis[i])continue;
        a[k]=i;
        vis[i]=true;
        dfs(k+1,n);
        vis[i]=false;
    }
}
int main()
{
    for(int i=1;i<=9;++i)
    {
        memset(vis,false,sizeof(vis));
        dfs(1,i);
    }
    printf("%d",ans);
    return 0;
}

Problem 42: Coded triangle numbers

（取 $n$ 为单词数量，$m$ 为所有单词对应数值的最大值）

【思路】我们在 Problem 22 中使用了文件输入索引，同时对其进行操作。这次我们直接将索引每十个元素空一行，并存放于数组中。

接着我们只需要枚举每个单词并判断它所对应的数值是否为三角形数即可。

判断是否为三角形数可以采用二分法，单次时间复杂度为 $\mathcal O(\log \sqrt m)$

总体时间复杂度为 $\mathcal O(n \log \sqrt m)$：

#include<stdio.h>
#include<stdbool.h>
int ans;
const char *s[]=
{
    "A","ABILITY","ABLE","ABOUT","ABOVE","ABSENCE","ABSOLUTELY","ACADEMIC","ACCEPT","ACCESS",
    "ACCIDENT","ACCOMPANY","ACCORDING","ACCOUNT","ACHIEVE","ACHIEVEMENT","ACID","ACQUIRE","ACROSS","ACT",
    "ACTION","ACTIVE","ACTIVITY","ACTUAL","ACTUALLY","ADD","ADDITION","ADDITIONAL","ADDRESS","ADMINISTRATION",
    "ADMIT","ADOPT","ADULT","ADVANCE","ADVANTAGE","ADVICE","ADVISE","AFFAIR","AFFECT","AFFORD",
    "AFRAID","AFTER","AFTERNOON","AFTERWARDS","AGAIN","AGAINST","AGE","AGENCY","AGENT","AGO",
    "AGREE","AGREEMENT","AHEAD","AID","AIM","AIR","AIRCRAFT","ALL","ALLOW","ALMOST",
    "ALONE","ALONG","ALREADY","ALRIGHT","ALSO","ALTERNATIVE","ALTHOUGH","ALWAYS","AMONG","AMONGST",
    "AMOUNT","AN","ANALYSIS","ANCIENT","AND","ANIMAL","ANNOUNCE","ANNUAL","ANOTHER","ANSWER",
    "ANY","ANYBODY","ANYONE","ANYTHING","ANYWAY","APART","APPARENT","APPARENTLY","APPEAL","APPEAR",
    "APPEARANCE","APPLICATION","APPLY","APPOINT","APPOINTMENT","APPROACH","APPROPRIATE","APPROVE","AREA","ARGUE",
    "ARGUMENT","ARISE","ARM","ARMY","AROUND","ARRANGE","ARRANGEMENT","ARRIVE","ART","ARTICLE",
    "ARTIST","AS","ASK","ASPECT","ASSEMBLY","ASSESS","ASSESSMENT","ASSET","ASSOCIATE","ASSOCIATION",
    "ASSUME","ASSUMPTION","AT","ATMOSPHERE","ATTACH","ATTACK","ATTEMPT","ATTEND","ATTENTION","ATTITUDE",
    "ATTRACT","ATTRACTIVE","AUDIENCE","AUTHOR","AUTHORITY","AVAILABLE","AVERAGE","AVOID","AWARD","AWARE",
    "AWAY","AYE","BABY","BACK","BACKGROUND","BAD","BAG","BALANCE","BALL","BAND",
    "BANK","BAR","BASE","BASIC","BASIS","BATTLE","BE","BEAR","BEAT","BEAUTIFUL",
    "BECAUSE","BECOME","BED","BEDROOM","BEFORE","BEGIN","BEGINNING","BEHAVIOUR","BEHIND","BELIEF",
    "BELIEVE","BELONG","BELOW","BENEATH","BENEFIT","BESIDE","BEST","BETTER","BETWEEN","BEYOND",
    "BIG","BILL","BIND","BIRD","BIRTH","BIT","BLACK","BLOCK","BLOOD","BLOODY",
    "BLOW","BLUE","BOARD","BOAT","BODY","BONE","BOOK","BORDER","BOTH","BOTTLE",
    "BOTTOM","BOX","BOY","BRAIN","BRANCH","BREAK","BREATH","BRIDGE","BRIEF","BRIGHT",
    "BRING","BROAD","BROTHER","BUDGET","BUILD","BUILDING","BURN","BUS","BUSINESS","BUSY",
    "BUT","BUY","BY","CABINET","CALL","CAMPAIGN","CAN","CANDIDATE","CAPABLE","CAPACITY",
    "CAPITAL","CAR","CARD","CARE","CAREER","CAREFUL","CAREFULLY","CARRY","CASE","CASH",
    "CAT","CATCH","CATEGORY","CAUSE","CELL","CENTRAL","CENTRE","CENTURY","CERTAIN","CERTAINLY",
    "CHAIN","CHAIR","CHAIRMAN","CHALLENGE","CHANCE","CHANGE","CHANNEL","CHAPTER","CHARACTER","CHARACTERISTIC",
    "CHARGE","CHEAP","CHECK","CHEMICAL","CHIEF","CHILD","CHOICE","CHOOSE","CHURCH","CIRCLE",
    "CIRCUMSTANCE","CITIZEN","CITY","CIVIL","CLAIM","CLASS","CLEAN","CLEAR","CLEARLY","CLIENT",
    "CLIMB","CLOSE","CLOSELY","CLOTHES","CLUB","COAL","CODE","COFFEE","COLD","COLLEAGUE",
    "COLLECT","COLLECTION","COLLEGE","COLOUR","COMBINATION","COMBINE","COME","COMMENT","COMMERCIAL","COMMISSION",
    "COMMIT","COMMITMENT","COMMITTEE","COMMON","COMMUNICATION","COMMUNITY","COMPANY","COMPARE","COMPARISON","COMPETITION",
    "COMPLETE","COMPLETELY","COMPLEX","COMPONENT","COMPUTER","CONCENTRATE","CONCENTRATION","CONCEPT","CONCERN","CONCERNED",
    "CONCLUDE","CONCLUSION","CONDITION","CONDUCT","CONFERENCE","CONFIDENCE","CONFIRM","CONFLICT","CONGRESS","CONNECT",
    "CONNECTION","CONSEQUENCE","CONSERVATIVE","CONSIDER","CONSIDERABLE","CONSIDERATION","CONSIST","CONSTANT","CONSTRUCTION","CONSUMER",
    "CONTACT","CONTAIN","CONTENT","CONTEXT","CONTINUE","CONTRACT","CONTRAST","CONTRIBUTE","CONTRIBUTION","CONTROL",
    "CONVENTION","CONVERSATION","COPY","CORNER","CORPORATE","CORRECT","COS","COST","COULD","COUNCIL",
    "COUNT","COUNTRY","COUNTY","COUPLE","COURSE","COURT","COVER","CREATE","CREATION","CREDIT",
    "CRIME","CRIMINAL","CRISIS","CRITERION","CRITICAL","CRITICISM","CROSS","CROWD","CRY","CULTURAL",
    "CULTURE","CUP","CURRENT","CURRENTLY","CURRICULUM","CUSTOMER","CUT","DAMAGE","DANGER","DANGEROUS",
    "DARK","DATA","DATE","DAUGHTER","DAY","DEAD","DEAL","DEATH","DEBATE","DEBT",
    "DECADE","DECIDE","DECISION","DECLARE","DEEP","DEFENCE","DEFENDANT","DEFINE","DEFINITION","DEGREE",
    "DELIVER","DEMAND","DEMOCRATIC","DEMONSTRATE","DENY","DEPARTMENT","DEPEND","DEPUTY","DERIVE","DESCRIBE",
    "DESCRIPTION","DESIGN","DESIRE","DESK","DESPITE","DESTROY","DETAIL","DETAILED","DETERMINE","DEVELOP",
    "DEVELOPMENT","DEVICE","DIE","DIFFERENCE","DIFFERENT","DIFFICULT","DIFFICULTY","DINNER","DIRECT","DIRECTION",
    "DIRECTLY","DIRECTOR","DISAPPEAR","DISCIPLINE","DISCOVER","DISCUSS","DISCUSSION","DISEASE","DISPLAY","DISTANCE",
    "DISTINCTION","DISTRIBUTION","DISTRICT","DIVIDE","DIVISION","DO","DOCTOR","DOCUMENT","DOG","DOMESTIC",
    "DOOR","DOUBLE","DOUBT","DOWN","DRAW","DRAWING","DREAM","DRESS","DRINK","DRIVE",
    "DRIVER","DROP","DRUG","DRY","DUE","DURING","DUTY","EACH","EAR","EARLY",
    "EARN","EARTH","EASILY","EAST","EASY","EAT","ECONOMIC","ECONOMY","EDGE","EDITOR",
    "EDUCATION","EDUCATIONAL","EFFECT","EFFECTIVE","EFFECTIVELY","EFFORT","EGG","EITHER","ELDERLY","ELECTION",
    "ELEMENT","ELSE","ELSEWHERE","EMERGE","EMPHASIS","EMPLOY","EMPLOYEE","EMPLOYER","EMPLOYMENT","EMPTY",
    "ENABLE","ENCOURAGE","END","ENEMY","ENERGY","ENGINE","ENGINEERING","ENJOY","ENOUGH","ENSURE",
    "ENTER","ENTERPRISE","ENTIRE","ENTIRELY","ENTITLE","ENTRY","ENVIRONMENT","ENVIRONMENTAL","EQUAL","EQUALLY",
    "EQUIPMENT","ERROR","ESCAPE","ESPECIALLY","ESSENTIAL","ESTABLISH","ESTABLISHMENT","ESTATE","ESTIMATE","EVEN",
    "EVENING","EVENT","EVENTUALLY","EVER","EVERY","EVERYBODY","EVERYONE","EVERYTHING","EVIDENCE","EXACTLY",
    "EXAMINATION","EXAMINE","EXAMPLE","EXCELLENT","EXCEPT","EXCHANGE","EXECUTIVE","EXERCISE","EXHIBITION","EXIST",
    "EXISTENCE","EXISTING","EXPECT","EXPECTATION","EXPENDITURE","EXPENSE","EXPENSIVE","EXPERIENCE","EXPERIMENT","EXPERT",
    "EXPLAIN","EXPLANATION","EXPLORE","EXPRESS","EXPRESSION","EXTEND","EXTENT","EXTERNAL","EXTRA","EXTREMELY",
    "EYE","FACE","FACILITY","FACT","FACTOR","FACTORY","FAIL","FAILURE","FAIR","FAIRLY",
    "FAITH","FALL","FAMILIAR","FAMILY","FAMOUS","FAR","FARM","FARMER","FASHION","FAST",
    "FATHER","FAVOUR","FEAR","FEATURE","FEE","FEEL","FEELING","FEMALE","FEW","FIELD",
    "FIGHT","FIGURE","FILE","FILL","FILM","FINAL","FINALLY","FINANCE","FINANCIAL","FIND",
    "FINDING","FINE","FINGER","FINISH","FIRE","FIRM","FIRST","FISH","FIT","FIX",
    "FLAT","FLIGHT","FLOOR","FLOW","FLOWER","FLY","FOCUS","FOLLOW","FOLLOWING","FOOD",
    "FOOT","FOOTBALL","FOR","FORCE","FOREIGN","FOREST","FORGET","FORM","FORMAL","FORMER",
    "FORWARD","FOUNDATION","FREE","FREEDOM","FREQUENTLY","FRESH","FRIEND","FROM","FRONT","FRUIT",
    "FUEL","FULL","FULLY","FUNCTION","FUND","FUNNY","FURTHER","FUTURE","GAIN","GAME",
    "GARDEN","GAS","GATE","GATHER","GENERAL","GENERALLY","GENERATE","GENERATION","GENTLEMAN","GET",
    "GIRL","GIVE","GLASS","GO","GOAL","GOD","GOLD","GOOD","GOVERNMENT","GRANT",
    "GREAT","GREEN","GREY","GROUND","GROUP","GROW","GROWING","GROWTH","GUEST","GUIDE",
    "GUN","HAIR","HALF","HALL","HAND","HANDLE","HANG","HAPPEN","HAPPY","HARD",
    "HARDLY","HATE","HAVE","HE","HEAD","HEALTH","HEAR","HEART","HEAT","HEAVY",
    "HELL","HELP","HENCE","HER","HERE","HERSELF","HIDE","HIGH","HIGHLY","HILL",
    "HIM","HIMSELF","HIS","HISTORICAL","HISTORY","HIT","HOLD","HOLE","HOLIDAY","HOME",
    "HOPE","HORSE","HOSPITAL","HOT","HOTEL","HOUR","HOUSE","HOUSEHOLD","HOUSING","HOW",
    "HOWEVER","HUGE","HUMAN","HURT","HUSBAND","I","IDEA","IDENTIFY","IF","IGNORE",
    "ILLUSTRATE","IMAGE","IMAGINE","IMMEDIATE","IMMEDIATELY","IMPACT","IMPLICATION","IMPLY","IMPORTANCE","IMPORTANT",
    "IMPOSE","IMPOSSIBLE","IMPRESSION","IMPROVE","IMPROVEMENT","IN","INCIDENT","INCLUDE","INCLUDING","INCOME",
    "INCREASE","INCREASED","INCREASINGLY","INDEED","INDEPENDENT","INDEX","INDICATE","INDIVIDUAL","INDUSTRIAL","INDUSTRY",
    "INFLUENCE","INFORM","INFORMATION","INITIAL","INITIATIVE","INJURY","INSIDE","INSIST","INSTANCE","INSTEAD",
    "INSTITUTE","INSTITUTION","INSTRUCTION","INSTRUMENT","INSURANCE","INTEND","INTENTION","INTEREST","INTERESTED","INTERESTING",
    "INTERNAL","INTERNATIONAL","INTERPRETATION","INTERVIEW","INTO","INTRODUCE","INTRODUCTION","INVESTIGATE","INVESTIGATION","INVESTMENT",
    "INVITE","INVOLVE","IRON","IS","ISLAND","ISSUE","IT","ITEM","ITS","ITSELF",
    "JOB","JOIN","JOINT","JOURNEY","JUDGE","JUMP","JUST","JUSTICE","KEEP","KEY",
    "KID","KILL","KIND","KING","KITCHEN","KNEE","KNOW","KNOWLEDGE","LABOUR","LACK",
    "LADY","LAND","LANGUAGE","LARGE","LARGELY","LAST","LATE","LATER","LATTER","LAUGH",
    "LAUNCH","LAW","LAWYER","LAY","LEAD","LEADER","LEADERSHIP","LEADING","LEAF","LEAGUE",
    "LEAN","LEARN","LEAST","LEAVE","LEFT","LEG","LEGAL","LEGISLATION","LENGTH","LESS",
    "LET","LETTER","LEVEL","LIABILITY","LIBERAL","LIBRARY","LIE","LIFE","LIFT","LIGHT",
    "LIKE","LIKELY","LIMIT","LIMITED","LINE","LINK","LIP","LIST","LISTEN","LITERATURE",
    "LITTLE","LIVE","LIVING","LOAN","LOCAL","LOCATION","LONG","LOOK","LORD","LOSE",
    "LOSS","LOT","LOVE","LOVELY","LOW","LUNCH","MACHINE","MAGAZINE","MAIN","MAINLY",
    "MAINTAIN","MAJOR","MAJORITY","MAKE","MALE","MAN","MANAGE","MANAGEMENT","MANAGER","MANNER",
    "MANY","MAP","MARK","MARKET","MARRIAGE","MARRIED","MARRY","MASS","MASTER","MATCH",
    "MATERIAL","MATTER","MAY","MAYBE","ME","MEAL","MEAN","MEANING","MEANS","MEANWHILE",
    "MEASURE","MECHANISM","MEDIA","MEDICAL","MEET","MEETING","MEMBER","MEMBERSHIP","MEMORY","MENTAL",
    "MENTION","MERELY","MESSAGE","METAL","METHOD","MIDDLE","MIGHT","MILE","MILITARY","MILK",
    "MIND","MINE","MINISTER","MINISTRY","MINUTE","MISS","MISTAKE","MODEL","MODERN","MODULE",
    "MOMENT","MONEY","MONTH","MORE","MORNING","MOST","MOTHER","MOTION","MOTOR","MOUNTAIN",
    "MOUTH","MOVE","MOVEMENT","MUCH","MURDER","MUSEUM","MUSIC","MUST","MY","MYSELF",
    "NAME","NARROW","NATION","NATIONAL","NATURAL","NATURE","NEAR","NEARLY","NECESSARILY","NECESSARY",
    "NECK","NEED","NEGOTIATION","NEIGHBOUR","NEITHER","NETWORK","NEVER","NEVERTHELESS","NEW","NEWS",
    "NEWSPAPER","NEXT","NICE","NIGHT","NO","NOBODY","NOD","NOISE","NONE","NOR",
    "NORMAL","NORMALLY","NORTH","NORTHERN","NOSE","NOT","NOTE","NOTHING","NOTICE","NOTION",
    "NOW","NUCLEAR","NUMBER","NURSE","OBJECT","OBJECTIVE","OBSERVATION","OBSERVE","OBTAIN","OBVIOUS",
    "OBVIOUSLY","OCCASION","OCCUR","ODD","OF","OFF","OFFENCE","OFFER","OFFICE","OFFICER",
    "OFFICIAL","OFTEN","OIL","OKAY","OLD","ON","ONCE","ONE","ONLY","ONTO",
    "OPEN","OPERATE","OPERATION","OPINION","OPPORTUNITY","OPPOSITION","OPTION","OR","ORDER","ORDINARY",
    "ORGANISATION","ORGANISE","ORGANIZATION","ORIGIN","ORIGINAL","OTHER","OTHERWISE","OUGHT","OUR","OURSELVES",
    "OUT","OUTCOME","OUTPUT","OUTSIDE","OVER","OVERALL","OWN","OWNER","PACKAGE","PAGE",
    "PAIN","PAINT","PAINTING","PAIR","PANEL","PAPER","PARENT","PARK","PARLIAMENT","PART",
    "PARTICULAR","PARTICULARLY","PARTLY","PARTNER","PARTY","PASS","PASSAGE","PAST","PATH","PATIENT",
    "PATTERN","PAY","PAYMENT","PEACE","PENSION","PEOPLE","PER","PERCENT","PERFECT","PERFORM",
    "PERFORMANCE","PERHAPS","PERIOD","PERMANENT","PERSON","PERSONAL","PERSUADE","PHASE","PHONE","PHOTOGRAPH",
    "PHYSICAL","PICK","PICTURE","PIECE","PLACE","PLAN","PLANNING","PLANT","PLASTIC","PLATE",
    "PLAY","PLAYER","PLEASE","PLEASURE","PLENTY","PLUS","POCKET","POINT","POLICE","POLICY",
    "POLITICAL","POLITICS","POOL","POOR","POPULAR","POPULATION","POSITION","POSITIVE","POSSIBILITY","POSSIBLE",
    "POSSIBLY","POST","POTENTIAL","POUND","POWER","POWERFUL","PRACTICAL","PRACTICE","PREFER","PREPARE",
    "PRESENCE","PRESENT","PRESIDENT","PRESS","PRESSURE","PRETTY","PREVENT","PREVIOUS","PREVIOUSLY","PRICE",
    "PRIMARY","PRIME","PRINCIPLE","PRIORITY","PRISON","PRISONER","PRIVATE","PROBABLY","PROBLEM","PROCEDURE",
    "PROCESS","PRODUCE","PRODUCT","PRODUCTION","PROFESSIONAL","PROFIT","PROGRAM","PROGRAMME","PROGRESS","PROJECT",
    "PROMISE","PROMOTE","PROPER","PROPERLY","PROPERTY","PROPORTION","PROPOSE","PROPOSAL","PROSPECT","PROTECT",
    "PROTECTION","PROVE","PROVIDE","PROVIDED","PROVISION","PUB","PUBLIC","PUBLICATION","PUBLISH","PULL",
    "PUPIL","PURPOSE","PUSH","PUT","QUALITY","QUARTER","QUESTION","QUICK","QUICKLY","QUIET",
    "QUITE","RACE","RADIO","RAILWAY","RAIN","RAISE","RANGE","RAPIDLY","RARE","RATE",
    "RATHER","REACH","REACTION","READ","READER","READING","READY","REAL","REALISE","REALITY",
    "REALIZE","REALLY","REASON","REASONABLE","RECALL","RECEIVE","RECENT","RECENTLY","RECOGNISE","RECOGNITION",
    "RECOGNIZE","RECOMMEND","RECORD","RECOVER","RED","REDUCE","REDUCTION","REFER","REFERENCE","REFLECT",
    "REFORM","REFUSE","REGARD","REGION","REGIONAL","REGULAR","REGULATION","REJECT","RELATE","RELATION",
    "RELATIONSHIP","RELATIVE","RELATIVELY","RELEASE","RELEVANT","RELIEF","RELIGION","RELIGIOUS","RELY","REMAIN",
    "REMEMBER","REMIND","REMOVE","REPEAT","REPLACE","REPLY","REPORT","REPRESENT","REPRESENTATION","REPRESENTATIVE",
    "REQUEST","REQUIRE","REQUIREMENT","RESEARCH","RESOURCE","RESPECT","RESPOND","RESPONSE","RESPONSIBILITY","RESPONSIBLE",
    "REST","RESTAURANT","RESULT","RETAIN","RETURN","REVEAL","REVENUE","REVIEW","REVOLUTION","RICH",
    "RIDE","RIGHT","RING","RISE","RISK","RIVER","ROAD","ROCK","ROLE","ROLL",
    "ROOF","ROOM","ROUND","ROUTE","ROW","ROYAL","RULE","RUN","RURAL","SAFE",
    "SAFETY","SALE","SAME","SAMPLE","SATISFY","SAVE","SAY","SCALE","SCENE","SCHEME",
    "SCHOOL","SCIENCE","SCIENTIFIC","SCIENTIST","SCORE","SCREEN","SEA","SEARCH","SEASON","SEAT",
    "SECOND","SECONDARY","SECRETARY","SECTION","SECTOR","SECURE","SECURITY","SEE","SEEK","SEEM",
    "SELECT","SELECTION","SELL","SEND","SENIOR","SENSE","SENTENCE","SEPARATE","SEQUENCE","SERIES",
    "SERIOUS","SERIOUSLY","SERVANT","SERVE","SERVICE","SESSION","SET","SETTLE","SETTLEMENT","SEVERAL",
    "SEVERE","SEX","SEXUAL","SHAKE","SHALL","SHAPE","SHARE","SHE","SHEET","SHIP",
    "SHOE","SHOOT","SHOP","SHORT","SHOT","SHOULD","SHOULDER","SHOUT","SHOW","SHUT",
    "SIDE","SIGHT","SIGN","SIGNAL","SIGNIFICANCE","SIGNIFICANT","SILENCE","SIMILAR","SIMPLE","SIMPLY",
    "SINCE","SING","SINGLE","SIR","SISTER","SIT","SITE","SITUATION","SIZE","SKILL",
    "SKIN","SKY","SLEEP","SLIGHTLY","SLIP","SLOW","SLOWLY","SMALL","SMILE","SO",
    "SOCIAL","SOCIETY","SOFT","SOFTWARE","SOIL","SOLDIER","SOLICITOR","SOLUTION","SOME","SOMEBODY",
    "SOMEONE","SOMETHING","SOMETIMES","SOMEWHAT","SOMEWHERE","SON","SONG","SOON","SORRY","SORT",
    "SOUND","SOURCE","SOUTH","SOUTHERN","SPACE","SPEAK","SPEAKER","SPECIAL","SPECIES","SPECIFIC",
    "SPEECH","SPEED","SPEND","SPIRIT","SPORT","SPOT","SPREAD","SPRING","STAFF","STAGE",
    "STAND","STANDARD","STAR","START","STATE","STATEMENT","STATION","STATUS","STAY","STEAL",
    "STEP","STICK","STILL","STOCK","STONE","STOP","STORE","STORY","STRAIGHT","STRANGE",
    "STRATEGY","STREET","STRENGTH","STRIKE","STRONG","STRONGLY","STRUCTURE","STUDENT","STUDIO","STUDY",
    "STUFF","STYLE","SUBJECT","SUBSTANTIAL","SUCCEED","SUCCESS","SUCCESSFUL","SUCH","SUDDENLY","SUFFER",
    "SUFFICIENT","SUGGEST","SUGGESTION","SUITABLE","SUM","SUMMER","SUN","SUPPLY","SUPPORT","SUPPOSE",
    "SURE","SURELY","SURFACE","SURPRISE","SURROUND","SURVEY","SURVIVE","SWITCH","SYSTEM","TABLE",
    "TAKE","TALK","TALL","TAPE","TARGET","TASK","TAX","TEA","TEACH","TEACHER",
    "TEACHING","TEAM","TEAR","TECHNICAL","TECHNIQUE","TECHNOLOGY","TELEPHONE","TELEVISION","TELL","TEMPERATURE",
    "TEND","TERM","TERMS","TERRIBLE","TEST","TEXT","THAN","THANK","THANKS","THAT",
    "THE","THEATRE","THEIR","THEM","THEME","THEMSELVES","THEN","THEORY","THERE","THEREFORE",
    "THESE","THEY","THIN","THING","THINK","THIS","THOSE","THOUGH","THOUGHT","THREAT",
    "THREATEN","THROUGH","THROUGHOUT","THROW","THUS","TICKET","TIME","TINY","TITLE","TO",
    "TODAY","TOGETHER","TOMORROW","TONE","TONIGHT","TOO","TOOL","TOOTH","TOP","TOTAL",
    "TOTALLY","TOUCH","TOUR","TOWARDS","TOWN","TRACK","TRADE","TRADITION","TRADITIONAL","TRAFFIC",
    "TRAIN","TRAINING","TRANSFER","TRANSPORT","TRAVEL","TREAT","TREATMENT","TREATY","TREE","TREND",
    "TRIAL","TRIP","TROOP","TROUBLE","TRUE","TRUST","TRUTH","TRY","TURN","TWICE",
    "TYPE","TYPICAL","UNABLE","UNDER","UNDERSTAND","UNDERSTANDING","UNDERTAKE","UNEMPLOYMENT","UNFORTUNATELY","UNION",
    "UNIT","UNITED","UNIVERSITY","UNLESS","UNLIKELY","UNTIL","UP","UPON","UPPER","URBAN",
    "US","USE","USED","USEFUL","USER","USUAL","USUALLY","VALUE","VARIATION","VARIETY",
    "VARIOUS","VARY","VAST","VEHICLE","VERSION","VERY","VIA","VICTIM","VICTORY","VIDEO",
    "VIEW","VILLAGE","VIOLENCE","VISION","VISIT","VISITOR","VITAL","VOICE","VOLUME","VOTE",
    "WAGE","WAIT","WALK","WALL","WANT","WAR","WARM","WARN","WASH","WATCH",
    "WATER","WAVE","WAY","WE","WEAK","WEAPON","WEAR","WEATHER","WEEK","WEEKEND",
    "WEIGHT","WELCOME","WELFARE","WELL","WEST","WESTERN","WHAT","WHATEVER","WHEN","WHERE",
    "WHEREAS","WHETHER","WHICH","WHILE","WHILST","WHITE","WHO","WHOLE","WHOM","WHOSE",
    "WHY","WIDE","WIDELY","WIFE","WILD","WILL","WIN","WIND","WINDOW","WINE",
    "WING","WINNER","WINTER","WISH","WITH","WITHDRAW","WITHIN","WITHOUT","WOMAN","WONDER",
    "WONDERFUL","WOOD","WORD","WORK","WORKER","WORKING","WORKS","WORLD","WORRY","WORTH",
    "WOULD","WRITE","WRITER","WRITING","WRONG","YARD","YEAH","YEAR","YES","YESTERDAY",
    "YET","YOU","YOUNG","YOUR","YOURSELF","YOUTH"
};
int main()
{
    for(int i=0;i<1786;++i)
    {
        int sum=0,l=1,r=30;
        bool flag=false;
        for(int j=0;s[i][j];++j)sum+=s[i][j]-'A'+1;
        sum<<=1;
        while(l<=r)
        {
            int mid=(l+r)>>1,tmp=mid*(mid+1);
            if(tmp==sum)
            {
                flag=true;
                break;
            }
            if(tmp>sum)r=mid-1;
            else l=mid+1;
        }
        ans+=flag;
    }
    printf("%d",ans);
    return 0;
}

Problem 43: Sub-string divisibility

（本题取 $n=10$）

【思路】构造 $0 \sim 9$ 全排列，然后合成十位数后判断即可，时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$：

#include<stdio.h>
#include<stdbool.h>
const int p[]={2,3,5,7,11,13,17};
long long ans;
int a[10];
bool vis[10];
void dfs(int k)
{
    if(k>9)
    {
        bool flag=true;
        for(int i=1;i<=7;++i)
        {
            int x=a[i]*100+a[i+1]*10+a[i+2];
            if(x%p[i-1])
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            long long x=0;
            for(int i=0;i<=9;++i)x=x*10+a[i];
            ans+=x;
        }
        return;
    }
    for(int i=0;i<=9;++i)
    {
        if(vis[i])continue;
        a[k]=i;
        vis[i]=true;
        dfs(k+1);
        vis[i]=false;
    }
}
int main()
{
    dfs(0);
    printf("%lld",ans);
    return 0;
}

Problem 44: Pentagon numbers

【思路】选定一个足够大的项数上限 $n$，然后 $\mathcal O(n^2)$ 枚举，判断的时候采用二分，总体时间复杂度为 $\mathcal O(n^2 \log n)$：

#include<stdio.h>
#include<stdbool.h>
int ans=1<<30;
bool check(int l,int r,int x)
{
    while(l<=r)
    {
        int mid=(l+r)>>1,tmp=mid*(3*mid-1);
        if(tmp==x)return true;
        if(tmp>x)r=mid-1;
        else l=mid+1;
    }
    return false;
}
int main()
{
    for(int i=1;i<=10000;++i)
    {
        for(int j=1;j<i;++j)
        {
            int pi=i*(i*3-1),pj=j*(j*3-1);
            if(check(1,i<<1,pi+pj)&&check(1,i,pi-pj)&&pi-pj<ans)ans=pi-pj;
        }
    }
    printf("%d",ans>>1);
    return 0;
}

Problem 45: Triangular, pentagonal, and hexagonal

【思路】不难发现三角形数必然是六边形数，因而我们可以从第 $144$ 项六边形数开始枚举，采用二分找到第一个既是五边形数又是六边形数的整数：

#include<stdio.h>
#include<stdbool.h>
#include<math.h>
bool check(long long l,long long r,long long x)
{
    while(l<=r)
    {
        long long mid=(l+r)>>1,tmp=mid*(mid*3-1);
        if(tmp==x)return true;
        if(tmp>x)r=mid-1;
        else l=mid+1;
    }
    return false;
}
int main()
{
    for(int i=144;;++i)
    {
        long long x=2LL*i*((i<<1)-1);
        if(check(1,sqrt(x),x))
        {
            printf("%lld",x>>1);
            return 0;
        }
    }
    return 0;
}

Problem 46: Goldbach’s other conjecture

【思路】取一个足够大的上限 $n$，确保最终答案不超过 $n$。我们可以采用欧拉筛得到所有的质数和合数表。注意合数不是按照顺序得到的，需要排序。

接着我们枚举所有在范围内的合数，二分找到不超过它的最大质数，然后判断二者之差是否能表示乘一个完全平方数的两倍即可。

总体时间复杂度为 $\mathcal O(n \log n)$：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
int prime[maxn],composite[maxn];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i*prime[j]&1)composite[++composite[0]]=i*prime[j];
            if(i%prime[j]==0)break;
        }
    }
    sort(composite+1,composite+composite[0]+1);
}
int binary(int l,int r,int x)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(prime[mid]>x)r=mid-1;
        else l=mid+1;
    }
    return r;
}
int main()
{
    euler();
    for(int i=1;i<=composite[0];++i)
    {
        int x=composite[i];
        bool flag=false;
        for(int j=binary(1,prime[0],x);j>1;--j)
        {
            int y=prime[j],z=sqrt((x-y)>>1);
            if(z*z<<1==x-y)
            {
                flag=true;
                break;
            }
        }
        if(!flag)
        {
            printf("%d",x);
            return 0;
        }
    }
    return 0;
}

Problem 47: Distinct primes factors

【思路】与 Problem 46 类似，我们先取一个足够大的上限 $n$，先欧拉筛得到质数表和合数表。

在判断合数是否有四个不同的质因数时，我们同样可以采取二分，找到不超过它的最大质数，然后倒着循环，统计出它的不同质因数个数即可。

总体时间复杂度为 $\mathcal O(n \log n)$：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000;
int prime[maxn],composite[maxn];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            composite[++composite[0]]=i*prime[j];
            if(i%prime[j]==0)break;
        }
    }
    sort(composite+1,composite+composite[0]+1);
}
int binary(int l,int r,int x)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(prime[mid]>x)r=mid-1;
        else l=mid+1;
    }
    return r-1;
}
bool check(int x)
{
    if(!vis[x])return false;
    int cnt=0,tmp=0;
    for(int i=binary(1,x,x);i;--i)
    {
        bool flag=false;
        while(x%prime[i]==0)
        {
            flag=true;
            x/=prime[i];
        }
        cnt+=flag;
        if(cnt==4)return x==1;
    }
    return false;
}
int main()
{
    euler();
    for(int i=1;i<=composite[0];++i)
    {
        int x=composite[i];
        if(check(x)&&check(x+1)&&check(x+2)&&check(x+3))
        {
            printf("%d",x);
            return 0;
        }
    }
    return 0;
}

Problem 48: Self powers

（本题取 $n=1000$，$m=10^{10}$)

【思路】Python 直接套 pow：

mod = int(1e10)
ans = 0
for i in range(1, 1001): ans = (ans + pow(i, i, mod)) % mod
print(ans)

也可以使用快速幂+龟速乘，时间复杂度为 $\mathcal O(n \log n \log m)$。当然快速乘可优化到 $\mathcal O(n \log n)$：

#include<stdio.h>
const long long mod=1e10;
long long ans;
long long mul(long long a,long long b)
{
    long long s=0;
    while(b)
    {
        if(b&1)s=(s+a)%mod;
        a=(a<<1)%mod;
        b>>=1;
    }
    return s;
}
long long power(long long a,long long b)
{
    long long s=1;
    while(b)
    {
        if(b&1)s=mul(s,a)%mod;
        a=mul(a,a)%mod;
        b>>=1;
    }
    return s;
}
int main()
{
    for(int i=1;i<=1000;++i)ans+=power(i,i);
    printf("%lld",ans%mod);
    return 0;
}

Problem 49: Prime permutations

【思路】先欧拉筛，然后枚举所有四位数的所有排列，最后去重后检验即可：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
int cnt,prime[maxn],a[5],b[5],ans[5];
bool vis[maxn],flag[5];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
void dfs(int k)
{
    if(k>4)
    {
        int x=0;
        for(int i=1;i<=4;++i)x=x*10+a[b[i]];
        if(!vis[x])ans[++cnt]=x;
        return;
    }
    for(int i=1;i<=4;++i)
    {
        if(flag[i])continue;
        b[k]=i;
        flag[i]=true;
        dfs(k+1);
        flag[i]=false;
    }
}
int main()
{
    euler();
    for(int i=1000;i<10000;++i)
    {
        a[1]=i/1000;
        a[2]=i/100%10;
        a[3]=i/10%10;
        a[4]=i%10;
        if(!a[1]||!a[2]||!a[3]||!a[4])continue;
        memset(flag,false,sizeof(flag));
        cnt=0;
        dfs(1);
        sort(ans+1,ans+cnt+1);
        cnt=unique(ans+1,ans+cnt+1)-ans-1;
        for(int j=1;j<=cnt;++j)
        {
            if(ans[j]==1487)continue;
            for(int k=j+1;k<=cnt;++k)
            {
                for(int l=k+1;l<=cnt;++l)
                {
                    if(ans[l]-ans[k]==ans[k]-ans[j])
                    {
                        printf("%d%d%d",ans[j],ans[k],ans[l]);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
int cnt,prime[maxn],a[5],ans[5];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    euler();
    for(int i=1000;i<10000;++i)
    {
        a[1]=i/1000;
        a[2]=i/100%10;
        a[3]=i/10%10;
        a[4]=i%10;
        if(!a[1]||!a[2]||!a[3]||!a[4])continue;
        cnt=0;
        do
        {
            int x=0;
            for(int i=1;i<=4;++i)x=x*10+a[i];
            if(!vis[x])ans[++cnt]=x;
        }while(next_permutation(a+1,a+5));
        sort(ans+1,ans+cnt+1);
        cnt=unique(ans+1,ans+cnt+1)-ans-1;
        for(int j=1;j<=cnt;++j)
        {
            if(ans[j]==1487)continue;
            for(int k=j+1;k<=cnt;++k)
            {
                for(int l=k+1;l<=cnt;++l)
                {
                    if(ans[l]-ans[k]==ans[k]-ans[j])
                    {
                        printf("%d%d%d",ans[j],ans[k],ans[l]);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

Problem 50: Consecutive prime sum

（本题取 $n=1000000$，$m$ 为不超过 $n$ 的质数个数）

【思路】欧拉筛初始化后，采用前缀和预处理，一旦超过 $n$ 就不再继续做下去，这样会减小后续枚举范围。

紧接着在所有质数中枚举作为起始质数，然后取连续的 $maxl+1$ 个质数得到它们的和（规定 $maxl$ 为当前最多质数的个数），再判断是否为质数即可。

总体时间复杂度为 $\mathcal O(n+m^2)$：

#include<stdio.h>
#include<stdbool.h>
const int maxn=1000000;
int cnt,ans,maxl,prime[maxn];
long long s[maxn];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    euler();
    s[1]=prime[1];
    for(int i=2;i<=prime[0];++i)
    {
        s[i]=s[i-1]+prime[i];
        if(s[i]>1000000)
        {
            cnt=i;
            break;
        }
    }
    for(int i=1;i<=cnt;++i)
    {
        int sum=0;
        for(int j=i+maxl+1;j<=cnt&&s[j]-s[i-1]<=maxn;++j)
        {
            if(!vis[s[j]-s[i-1]])
            {
                maxl=j-i;
                ans=s[j]-s[i-1];
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Problem 51: Prime digit replacements

（本题取 $n=1000000$）

【思路】欧拉筛初始化后，对位数及空缺位置进行枚举，再分别判断 $0 \sim 9$ 填入之后是否为质数即可。

其中，在枚举方面，我们可以在 $0 \sim 9$ 之外新建一个特殊位 $10$，表示这个位置是待替换的。这样，我们的程序就无形之间被简化了。

总体时间复杂度为 $\mathcal O(n)$：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000;
int a[7],ans=1<<30,prime[maxn];
bool vis[maxn];
void euler()
{
    vis[0]=vis[1]=true;
    for(int i=2;i<=maxn;++i)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<=maxn&&j<=prime[0];++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    euler();
    for(int i=2,j=11;i<=6;++i,j*=11)
    {
        for(int k=j;k<j*11;++k)
        {
            int kk=k;
            bool flag=false;
            for(int l=i;l;--l)
            {
                a[l]=kk%11;
                flag|=(a[l]==10);
                kk/=11;
            }
            if(!flag)continue;
            int cnt=0,x;
            for(int l=9;l>=0;--l)
            {
                if(!l&&a[1]==10)break;
                x=0;
                for(int m=1;m<=i;++m)x=(x<<3)+(x<<1)+(a[m]==10?l:a[m]);
                cnt+=(!vis[x]);
            }
            if(cnt==8)ans=min(ans,x);
        }
        if(ans!=1<<30)break;
    }
    printf("%d",ans);
    return 0;
}

52. Permuted multiples

（本题取 $n=142857$）

【思路】从 $1$ 开始向更大的数进行枚举，利用 Python 整型字符串自由转换的功能进行判断，找到符合题意的数即可输出。

总体时间复杂度为 $\mathcal O(n)$：

i = 1
while True:
    a = []
    for j in range(1, 7):
        s = []
        k = str(i * j)
        for c in k:
            s.append(c)
        s.sort()
        a.append(s)
    flag = True
    for j in range(1, 6):
        if a[j] != a[j - 1]:
            flag = False
            break
    if flag:
        print(i)
        exit()
    i += 1

欧拉计划完整版题解

https://hensier.github.io/projecteuler/report/

作者

hensier

发布于

2022-05-02

更新于

2023-01-02

许可协议

#欧拉计划

欧拉计划完整版题解

Problem 1: Multiples of 3 and 5

Problem 2: Even Fibonacci numbers

Problem 3: Largest prime factor

Problem 4: Largest palindrome product

Problem 5: Smallest multiple

Problem 6: Sum square difference

Problem 7: 10001st prime

Problem 8: Largest product in a series

Problem 9: Special Pythagorean triplet

Problem 10: Summation of primes

Problem 11: Largest product in a grid

Problem 12: Highly divisible triangular number

Problem 13: Large sum

Problem 14: Longest Collatz sequence

Problem 15: Lattice paths

Problem 16: Power digit sum

Problem 17: Number letter counts

Problem 18: Maximum path sum I

Problem 19: Counting Sundays

Problem 20: Factorial digit sum

Problem 21: Amicable numbers

Problem 22: Names scores

Problem 23: Non-abundant sums

Problem 24: Lexicographic permutations

Problem 25: 1000-digit Fibonacci number

Problem 26: Reciprocal cycles

Problem 27: Quadratic primes

Problem 28: Number spiral diagonals

Problem 29: Distinct powers

Problem 30: Digit fifth powers

Problem 31: Coin sums

Problem 32: Pandigital products

Problem 33: Digit cancelling fractions

Problem 34: Digit factorials

Problem 35: Circular primes

Problem 36: Double-base palindromes

Problem 37: Truncatable primes

Problem 38: Pandigital multiples

Problem 39: Integer right triangles

Problem 40: Champernowne’s constant

Problem 41: Pandigital prime

Problem 42: Coded triangle numbers

Problem 43: Sub-string divisibility

Problem 44: Pentagon numbers

Problem 45: Triangular, pentagonal, and hexagonal

Problem 46: Goldbach’s other conjecture

Problem 47: Distinct primes factors

Problem 48: Self powers

Problem 49: Prime permutations

Problem 50: Consecutive prime sum

Problem 51: Prime digit replacements

52. Permuted multiples

作者

发布于

更新于

许可协议

评论

链接

最新文章

归档

标签