Problem 111
Search for 10-digit primes containing the maximum number of repeated digits.
M(n,d)是n位数的素数中,数字d最多重复次数
N(n,d)是n位数的素数中,数字d重复M(n,d)次的素数个数
S(n,d)是那N(n,d)个素数的和
求d=0 to 9的S(10,d)的和

既然要某数字重复次数最多嘛…当然从重复次数为n开始枚举到1为止
比如当前枚举到重复次数为k,枚举到的数字是d
那么构造出所有重复次数为k的n位数,然后判断是不是质数
只要找到一个质数,那么就能确定k是M(n,d)了,比k小的就不必枚举了
这里每个d来说k都十分接近n…也许普遍都是吧?…于是候选的数字个数也非常少
判断质数就用miller_rabin了

#include<stdio.h>
#include<algorithm>
using namespace std;
#include"miller.h"
/*
Project Euler 111
构造数,然后用miller_rabin来判素数
*/
#define N 10
int main(){
    char str[N+1];
    char sp[9];
    long d;
    str[N]=0;
    I sum=0;
    for(d=0;d<10;d++){
        long md=N-1,found=0,count=0;
        while(md>0&&(!found)){
            long i,j,nv=N-md,v=1;
            for(i=0;i<nv;i++)v*=10;
            sprintf(sp,"%%0%ldld",nv);
            for(i=0;i<v;i++){
                sprintf(str,sp,i);
                for(j=0;j<nv;j++){
                    if(str[j]=='0'+d)break;
                    if(j&&str[j]<str[j-1])break;
                }
                if(j<nv)continue;
                for(j=nv;j<N;j++)str[j]='0'+d;
                sort(str,str+N);
                do{
                    if(str[0]!='0'){
                        I val;
                        sscanf(str,"%I64d",&val);
                        if((val&1)&&miller_rabin(val,10)){
                            //printf("%s\n",str);
                            found=1;
                            count++;
                            sum+=val;
                        }
                    }
                }while(next_permutation(str,str+N));
            }
            md--;
        }
        printf("%ld:%I64d,%ld,%ld\n",d,sum,count,md+1);
    }
    printf("%I64d\n",sum);
    getchar();
    return 0;
}

Problem 112
Investigating the density of “bouncy” numbers.
bouncy数定义为:一个数的各位上的数没有单调性(非严格)
求最小的n,使得1~n中bouncy数的个数正好为n的99%

这个…直接从1开始枚举…依次计算每个数是不是bouncy数…
同时记录下从1到当前数总共有多少个bouncy数…
一旦这个数量达到目标就停下来输出…很简单的

Problem 113
How many numbers below a googol (10¹⁰⁰) are not “bouncy”?
这题…让我想起据说Google最初想要叫googol…结果拿到了给google的支票…于是改名?
问1~10^100中有多少非bouncy数

那就计算所有非增的和非降的数就是了…来个dp
dp[n][digit]表示n位数最后一位是digit的{非降|非增}数有多少
我分成了2次来计算,分别计算非降的和非增的
所以如果所有位都相同的话即是非增的也是非降的…所以要减去这种情况

#include<stdio.h>
/*
Project Euler 113
10^100中有多少非Boncy数
非boncy数是各位非增或非减的
dp[剩余位数][digit]
*/
#define I __int64
#define R "%I64d"
#define N 100
I inc[N][10],dec[N][10];
int main(){
    long i,j;
    for(i=0;i<10;i++)inc[0][i]=dec[0][i]=1;
    for(i=1;i<N;i++){
        I sum=0;
        for(j=9;j>=0;j--){
            sum+=inc[i-1][j];
            inc[i][j]=sum;
        }
        sum=0;
        for(j=0;j<10;j++){
            sum+=dec[i-1][j];
            dec[i][j]=sum;
        }
    }
    I ans=0;
    for(j=N-1;j>=0;j--){
        for(i=1;i<10;i++)
            ans+=inc[j][i]+dec[j][i];
        ans-=9;
    }
    printf(R"\n",ans);
    getchar();
    return 0;
}

Problem 114
Investigating the number of ways to fill a row with separated blocks that are at least three units long.
50个格子的长条,用长为1格黑色的或长度至少三格以上红色的填充
如果出现连续多个红色的话会被视为一个
问有多少种填法

简单的dp
dp[len]=方法数
每次填入1(黑)或者至少4(3红+1黑)
以及全是红的情况

#include<stdio.h>
/*
Project Euler 114
50个格子的长条,用长为1格黑色的或长度至少三格以上红色的填充
问有多少种填法

dp[len]=方法数
*/
#define I __int64
#define R "%I64d"
I dp[60];
int main(){
    long i;
    dp[0]=1;
    for(i=1;i<=50;i++){
        long j;
        dp[i]=dp[i-1];
        for(j=4;j<=i;j++)dp[i]+=dp[i-j];
        if(i>=3)dp[i]++;
    }
    printf(R"\n"R"\n",dp[7],dp[50]);
    getchar();
    return 0;
}

Problem 115
Finding a generalisation for the number of ways to fill a row with separated blocks.
这题是Problem 114的加强版
F(m,n)表示长度为n格的长条与最短为m的红色长条
求最小的n使得F(50,n)超过一百万

哪有加强嘛…只不过把红色最短的限制从3提升到了50而已…
老样子做就行了

#include<stdio.h>
/*
Project Euler 115
114题的略加强版
*/
long dp[999];
int main(){
    dp[0]=1;
    long i,j,m=50;
    for(i=1;;i++){
        dp[i]=dp[i-1];
        if(i>=m)dp[i]++;
        for(j=m+1;j<=i;j++)dp[i]+=dp[i-j];
        if(dp[i]>1000000)break;
    }
    printf("%ld:%ld\n",i,dp[i]);
    getchar();
    return 0;
}