ProjectEuler 1-60题解

发表于 | 分类于 |
字数统计: 7,079 字

探索新领域

PE前面的题还是很比较简单的。
除了某些题（如51，60）需要一定的枚举策略之外，其他题大部分靠暴力即可。

PE1

直接枚举即可。

1
2
3
4
5
6
7
void solve(){
    int sum = 0;
    for(int i = 3; i < 1000; ++i)
        if(i % 3 == 0 || i % 5 == 0)
            sum += i;
    printf("%d\n", sum);
}

答案：233168

PE2

直接枚举即可。

1
2
3
4
5
6
7
8
9
10
11
int fib[1005];
void solve(){
    int i, sum = 0;
    fib[0] = 1, fib[1] = 2;
    for(i = 2; fib[i - 1] < 4000000; ++i)
        fib[i] = fib[i - 1] + fib[i - 2];
    for(; i >= 0; --i)
        if(fib[i] <= 4000000 && fib[i] % 2 == 0)
            sum += fib[i];
    printf("%d\n", sum);
}

答案：4613732

PE3

本来可以直接上Pollard-Rho，后来想了一下其实不用。因为这个数还是比较小的。

1
2
3
4
5
6
7
8
9
10
11
ll c = 600851475143;
void solve(){
    ll tmp = c;
    for(ll i = 2; i * i <= c; ++i)
        if(tmp % i == 0){
            while(tmp % i == 0 && tmp / i != 1)
                tmp /= i;
            if(tmp / i == 1)break ;
        }
    printf("%d\n", tmp);
}

答案：6857

PE4

枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isP(int t){
    char s[8];
    sprintf(s, "%d", t);
    int len = strlen(s);
    for(int i = 0; i < (len >> 1); ++i)
        if(s[i] != s[len - i -1])
            return false;
    return true;
}
void solve(){
    int ans = 0;
    for(int i = 100; i < 1000; ++i)
        for(int j = 100; j < 1000; ++j)
            if(isP(i * j))
                ans = max(ans, i * j);
    printf("%d\n", ans);
}

答案：906609

PE5

可以手算出答案。
答案：232792560

PE6

直接手算即可。
答案：25164150

PE7

直接用筛法计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool vis[1000005] = {0};
int sum = 0;
void solve(){
    int N = 1000000;
    for(int i = 2; i <= N; ++i){
        if(!vis[i]){
            sum++;
            if(sum == 10001)printf("%d\n", i);
            for(int j = i + i; j <= N; j += i)
                vis[j] = 1;
        }
    }
}

答案：104743

PE8

直接遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char num[1005];
ll ans = 0;
void init(){
    for(int i = 0; i < 20; ++i)
        scanf("%s", num + i * 50);
}
void solve(){
    for(int i = 0; i <= 987; ++i){
        ll pro = 1;
        for(int j = 0; j < 13; ++j)
            pro *= (ll)(num[i + j] - '0');
        ans = max(ans, pro);
    }
    printf("%lld\n", ans);
}

答案：23514624000

PE9

直接循环遍历，枚举即可。

1
2
3
4
5
6
7
8
9
10
11
ll ans;
void solve(){
    for(int i = 3; i <= 1000; ++i)
        for(int j = 3; j <= 1000; ++j)
            if(i * i + j * j == (1000 - i - j) * (1000 - i - j) && 1000 > i + j){
                ans = 1ll * i * j * (1000 - i - j);
                goto printans;
            }
    printans:
    printf("%lld\n", ans);
}

答案：31875000

PE10

使用筛法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool vis[2000005] = {0};
ll sum = 0;
void solve(){
    int N = 2000000;
    for(int i = 2; i <= N; ++i){
        if(!vis[i]){
            sum += (ll)i;
            for(int j = i + i; j <= N; j += i)
                vis[j] = 1;
        }
    }
    printf("%lld\n", sum);
}

答案：142913828922

PE11

枚举即可。
一个数只需要枚举4个方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int dat[25][25];
void init(){
    for(int i = 0; i < 20; ++i)
        for(int j = 0; j < 20; ++j)
            dat[i][j] = read();
}
void solve(){
    int ans = 0;
    for(int i = 0; i < 20; ++i)
        for(int j = 0; j < 20; ++j){
            if(i >= 3){
                int t = 1;
                for(int k = 0; k < 4; ++k)
                    t *= dat[i - k][j];
                ans = max(ans, t);
            }
            if(j >= 3){
                int t = 1;
                for(int k = 0; k < 4; ++k)
                    t *= dat[i][j - k];
                ans = max(ans, t);
            }
            if(i >= 3 && j >= 3){
                int t = 1;
                for(int k = 0; k < 4; ++k)
                    t *= dat[i - k][j - k];
                ans = max(ans, t);
            }
            if(i >= 3 && j <= 16){
                int t = 1;
                for(int k = 0; k < 4; ++k)
                    t *= dat[i - k][j + k];
                ans = max(ans, t);
            }
        }
    printf("%d\n", ans);
}

答案：70600674

PE12

直接枚举每一个三角形数的因子即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int getD(ll t){
    int cnt = 0;
    ll i;
    for(i = 1; i * i < t; ++i)
        if(t % i == 0)
            cnt += 2;
    if(i * i == t)cnt++;
    return cnt;
}
void solve(){
    ll t, n;
    for(n = 11; ; ++n){
        t = n * (n + 1) >> 1;
        if(getD(t) > 500)
            break;
    }
    printf("%lld\n", t);
}

答案：76576500

PE13

用python水过去

1
2
3
4
5
6
y = 0
for i in range(1, 101, 1):
    x = input()
    y = y + x

print(y)

答案：5537376230

PE14

直接跑递归即可。
看清题目，问的是什么数产生最长链而不是最长链有多长！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int step[1000005] = {0}, ans = 0, maxi;
int go(ll cur){
    if(cur <= 1000000 && step[cur])
        return step[cur];
    int res;
    if(cur & 1)
        res = go(cur * 3 + 1) + 1;
    else
        res = go(cur >> 1) + 1;
    if(cur <= 1000000)
        step[cur] = res;
    return res;
}
void solve(){
    step[1] = 1;
    for(int i = 2; i <= 1000000; ++i){
        go(i);
        if(step[i] > ans)
            ans = step[i], maxi = i;
    }
    printf("%d\n", maxi);
}

答案：837799

PE15

即为
答案：137846528820

PE16

用python水过

1
2
3
4
5
6
7
x = 2 ** 1000
sum = 0
while x > 0:
    sum += x % 10
    x /= 10

print(sum)

答案：1366

PE17

神奇模拟题。
了解一下英式的读数字方式即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int ge[] = {0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 9, 8, 8};
int ten[] = {0, 0, 6, 6, 5, 5, 5, 7, 6, 6};
void solve(){
    int sum = 0;
    for(int i = 1; i < 1000; ++i){
        if(i < 20)
            sum += ge[i];
        else if(i < 100)
            sum += ge[i % 10] + ten[i / 10];
        else {
            sum += ge[i / 100] + 7;
            if(i % 100 != 0){
                sum += 3;//and
                if(i % 100 < 20)
                    sum += ge[i % 100];
                else 
                    sum += ge[i % 10] + ten[(i % 100) / 10];
            }
        }
    }
    printf("%d\n", sum + 11);//one thousand
}

答案：21124

PE18

一个简单的DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int dat[17][17] = {0};
int dp[17][17] = {0};
void init(){
    for(int i = 1; i <= 15; ++i)
        for(int j = 1; j <= i; ++j)
            dat[i][j] = read();
}
void solve(){
    for(int i = 1; i <= 15; ++i)
        for(int j = 1; j <= i; ++j)
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + dat[i][j];
    int ans = 0;
    for(int i = 1; i <= 15; ++i)
        ans = max(ans, dp[15][i]);
    printf("%d\n", ans);
}

答案：1074

PE19

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void solve(){
    int cury = 1901, curm = 1, curd = 1, curx = 2, ans = 0;
    for(; ; ){
        curd++, curx++;
        if(curd > month[curm]){
            if(curm != 2){
                curm++, curd = 1;
            }else{
                if(cury % 4 != 0)
                    curm++, curd = 1;
                else if(curd == 30)
                    curm++, curd = 1;
            }
        }
        if(curm == 13)
            cury++, curm = 1;
        if(cury > 2000)break;
        if(curx == 8)curx = 1;
        if(curx == 7 && curd == 1)ans++;
    }
    printf("%d\n", ans);
}

答案：171

PE20

用python水过

1
2
3
4
5
6
7
8
9
10
x = 1
for i in range(2, 101, 1):
    x *= i

ans = 0
while x > 0:
    ans += x % 10
    x /= 10

print(ans)

答案：648

PE21

遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ans = 0;
int d(int x){
    int res = 0, i = 1;
    for(i = 1; i * i < x; ++i)
        if(x % i == 0)
            res += i + x / i;
    if(i * i == x)res += i;
    return res - x;
}
void solve(){
    for(int i = 2; i < 10000; ++i){
        int dd = d(i);
        if(dd != i && d(dd) == i)
            ans += i + dd;
    }
    printf("%d\n", ans >> 1);
}

答案：31626

PE22

用string排序后水过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
char s[105];
string ss[10005];
int n = 0;
void solve(){
    for(; ; ){
        char c = getchar();
        if(c == EOF)break;
        int i = 0;
        while((c = getchar()) != '"')
            s[i++] = c;
        s[i] = '\0';
        getchar();
        n++;
        ss[n] = s;
    }
    sort(ss + 1, ss + n + 1);
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        int len = ss[i].length(), sum = 0;
        for(int j = 0; j < len; ++j)
            sum += ss[i][j] - 'A' + 1;
        ans += 1ll * sum * i;
    }
    printf("%lld\n", ans);
}

答案：871198282

PE23

暴力水过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int d[30005] = {0}, lis[30005], tot = 0;
bool vis[30005] = {0};
void init(){
    for(int i = 1; i <= 28123; ++i){
        int j;
        for(j = 1; j * j < i; ++j)
            if(i % j == 0)
                d[i] += j + i / j;
        if(j * j == i)d[i] += j;
        d[i] -= i;
        if(d[i] > i)
            lis[++tot] = i;
    }
}
void solve(){
    for(int i = 1; i <= tot; ++i)
        for(int j = i; j <= tot; ++j)
            if(lis[i] + lis[j] <= 28123)
                vis[lis[i] + lis[j]] = 1;
    int ans = 0;
    for(int i = 1; i <= 28123; ++i)
        if(!vis[i])
            ans += i;
    printf("%d\n", ans);
}

答案：4179871

PE24

大力next_permutation
答案：2783915460

PE25

用python水过。

1
2
3
4
5
6
7
8
9
10
11
12
x = 1
y = 1
ind = 2
while True:
    z = x + y
    x = y
    y = z
    ind += 1
    if len(str(z)) == 1000:
        break

print(ind)

答案：4782

PE26

当余数出现循环时终止即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lis[1005], tot, cur[1005];
int ans = 0, maxi;
void solve(){
    for(int i = 11; i < 1000; ++i){
        int t = 10;
        memset(cur, 0, sizeof(cur));
        for(tot = 1; ; ++tot){
            lis[tot] = t / i;
            if(!cur[t % i])
                cur[t % i] = tot;
            else{
                if(ans < tot - cur[t % i])
                    ans = tot - cur[t % i],
                    maxi = i;
                break ;
            }
            t %= i;
            t *= 10;
        }
    }
    printf("%d %d\n", ans, maxi);
}

答案：983

PE27

枚举即可。
注意负数不能算质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int ans = 0, maxi;
bool isP(int x){
    if(x <= 1)return false;
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0)
            return false;
    return true;
}
void solve(){
    for(int a = -999; a < 1000; ++a){
        for(int b = 2; b <= 1000; ++b){
            int n;
            for(n = 0; ; ++n)
                if(!isP(n * n + a * n + b))
                    break;
            if(n > ans)
                ans = n, maxi = a * b;
        }
    }
    printf("%d\n", maxi);
}

答案：-59231

PE28

模拟出蛇形数阵即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int d[1005][1005] = {0};
int dx[] = {1, 0, -1, 0, 0}, dy[] = {0, -1, 0, 1, 1};
void solve(){
    int x = 501, y = 502, c = 2;
    d[501][501] = 1;
    for(int i = 2; i <= 1000; i += 2){
        for(int j = 0; j < 4; ++j){
            for(int k = 0; k < i; ++k)
                d[x][y] = c,
                c++, x += dx[j], y += dy[j];
            x -= dx[j], y -= dy[j];
            x += dx[j + 1], y += dy[j + 1];
        }
    }
    int sum = 0;
    for(int i = 1; i <= 1001; ++i)
        sum += d[i][i] + d[i][1002 - i];
    printf("%d\n", sum - 1);
}

答案：669171001

PE29

用对数表示幂，排序去重即可。
会有奇怪的精度问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double d[10005];
int tot = 0, ans = 0;
bool cmp(const double& d1, const double& d2){
    return abs(d1 - d2) < 1e-5;
}
void solve(){
    for(int i = 2; i <= 100; ++i)
        for(int j = 2; j <= 100; ++j)
            d[tot++] = 100.0 * j * log(i);
    sort(d, d + tot);
    double cur = -1;
    for(int i = 0; i < tot; ++i)
        if(!cmp(cur, d[i]))
            cur = d[i], ans++;
    printf("%d\n", ans);
}

答案：9183

PE30

枚举即可。
上界小于1000000

1
2
3
4
5
6
7
8
9
10
11
12
13
int sum = 0;
int qq(int x){
    return x * x * x * x * x;
}
void solve(){
    for(int i = 2; i <= 1000000; ++i){
        int t = i, s = 0;
        while(t)
            s += qq(t % 10), t /= 10;
        if(s == i)sum += i;
    }
    printf("%d\n", sum);
}

答案：443839

PE31

多重背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int w[] = {1, 2, 5, 10, 20, 50, 100, 200};
int f[205] = {0};
void solve(){
    f[0] = 1;
    for(int i = 0; i < 8; ++i){
        for(int j = 1; ; j <<= 1){
            int d = j * w[i];
            if(d > 200)break ;
            for(int k = 200; k >= d; --k)
                f[k] += f[k - d];
        }
    }
    printf("%d\n", f[200]);
}

答案：73682

PE32

从1234开始枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int cnt[11];
bool f(int x){
    bool flag = 1;
    while(x){
        if(cnt[x % 10] || x % 10 == 0)
            flag = 0;
        cnt[x % 10]++,
        x /= 10;
    }
    return flag;
}
void t(int x){
    while(x)
        cnt[x % 10]--, x /= 10;
}
void solve(){
    int ans = 0;
    for(int i = 1234; i < 1000000; ++i){
        for(int j = 1; j < 10; ++j)
            cnt[j] = 0;
        if(!f(i))continue ;
        for(int j = 2; j * j < i; ++j){
            if(i % j == 0){
                if(!f(j)){
                    t(j);
                    continue ;
                }else{
                    if(!f(i / j)){
                        t(i / j), t(j);
                        continue;
                    }else{
                        int flag = 1;
                        for(int i = 1; i < 10; ++i)
                            if(cnt[i] != 1){
                                flag = 0;
                                break;
                            }
                        if(flag){
                            printf("%d %d %d\n", i, j, i / j);
                            ans += i;
                            break ;
                        }else {
                            t(j), t(i / j);
                            continue;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
}

答案：45228

PE33

枚举分子分母即可。
题意有点不太好懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve(){
    int fz = 1, fm = 1, cnt = 0;
    for(int i = 10; i <= 99; ++i)
        for(int j = i + 1; j <= 99; ++j){
            if(i % 10 == 0 && j % 10 == 0)
                continue ;
            int a = i / 10, b = i % 10, c = j / 10, d = j % 10;
            if(a == c){
                if(i * d == j * b)
                    fz *= i, fm *= j, cnt++;
            }else if(a == d){
                if(i * c == j * b)
                    fz *= i, fm *= j, cnt++;
            }else if(b == c){
                if(i * d == j * a)
                    fz *= i, fm *= j, cnt++;
            }else if(b == d){
                if(i * c == j * a)
                    fz *= i, fm *= j, cnt++;
            }
        }
    printf("%d %d\n", fm / gcd(fm, fz), cnt);
}

答案：100

PE34

枚举即可
只有2个数符合。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
void solve(){
    ll ans = 0;
    for(int i = 10; i <= 100000000; ++i){
        int t = i, sum = 0;
        while(t)
            sum += f[t % 10],
            t /= 10;
        if(sum == i)
            ans += 1ll * i,
            printf("%d\n", i);
    }
    printf("%lld\n", ans);
}

答案：40730

PE35

循环枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool vis[1000005] = {0};
char s[16];
void getP(){
    for(int i = 2; i <= 1000000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 1000000; j += i)
                vis[j] = 1;
        }
}
void solve(){
    getP();
    int ans = 13;
    for(int i = 111; i < 1000000; i += 2){
        if(vis[i])continue;
        sprintf(s, "%d", i);
        int len = strlen(s), j;
        sprintf(s + len, "%d", i);
        for(j = len; j > 0; --j){
            s[j + len] = '\0';
            if(vis[atoi(s + j)])
                break ;
        }
        if(!j)ans++;
    }
    printf("%d\n", ans);
}

答案：55

PE36

直接枚举回文数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll sum = 0;
int d[30];
bool isP(int x){
    int t = x, cnt = 0;
    while(t)
        d[cnt++] = t % 10, t /= 10;
    for(int i = 0; i < (cnt >> 1); ++i)
        if(d[i] != d[cnt - i - 1])
            return false;
    t = x, cnt = 0;
    while(t)
        d[cnt++] = t % 2, t >>= 1;
    for(int i = 0; i < (cnt >> 1); ++i)
        if(d[i] != d[cnt - i - 1])
            return false;
    return true;
}
void solve(){
    for(int i = 1; i < 1000000; i += 2)
        if(isP(i))
            sum += 1ll * i;
    printf("%lld\n", sum);
}

答案：872187

PE37

枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int sum = 0, ten[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
bool isP(int x){
    if(x <= 1)return false;
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0)
            return false;
    return true;
}
bool is(int x){
    int t = x;
    if(!isP(x))return false;
    for(; ; ){
        t /= 10;
        if(!t)break;
        if(!isP(t))return false;
    }
    int m;
    for(m = 1; ten[m] < x; m++)
        ;
    for(m--; m > 0; --m){
        x %= ten[m];
        if(!isP(x))return false;
    }
    return true;
}
void solve(){
    int cnt = 0;
    for(int i = 11; cnt < 11 && i < 1000000; i += 2){
        if(i % 10 != 3 && i % 10 != 7)
            continue ;
        if(is(i))
            cnt++, sum += i, printf("%d\n", i);
    }
    printf("%d\n", sum);
}

答案：748317

PE38

枚举这样的数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int ans = 0;
bool vis[11];
void solve(){
    char s[15];
    for(int i = 2; i < 10000; ++i){
        memset(vis, 0, sizeof(vis));
        int cnt = 0, flag = 1, j;
        for(j = 1; flag && cnt < 9 && j < 10; ++j){
            int t = i * j;
            while(t){
                if(t % 10 == 0 || vis[t % 10]){
                    flag = 0;
                    break;
                }else
                    vis[t % 10] = 1, cnt++,
                    t /= 10;
            }
        }
        if(cnt == 9 && flag){
            s[0] = '\0';
            for(int k = 1, st = 0; k < j; ++k)
                sprintf(s + st, "%d", k * i),
                st = strlen(s);
            ans = max(ans, atoi(s));
        }
    }
    printf("%d\n", ans);
}

答案：932718654

PE39

循环枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ans = 0, maxi;
void solve(){
    for(int i = 12; i <= 1000; ++i){
        int cnt = 0;
        for(int j = 3; j <= i / 3; ++j){
            for(int k = j + 1; k < i - j - j && k < (i - j) >> 1; ++k)
                if(j * j + k * k == (i - j - k) * (i - j - k))
                    cnt++;
            if(cnt > ans)
                ans = cnt, maxi = i;
        }
    }
    printf("%d\n", maxi);
}

答案：840

PE40

貌似只能枚举。。。
数据还特别大。跑了几分钟才跑出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int len = 0;
char s[1000105];
int c(int x){
    return s[x - 1] - '0';
}
void solve(){
    s[0] = '\0';
    for(int i = 1; len < 1000000; ++i){
        sprintf(s + len, "%d", i);
        if(i < 10)len++;
        else if(i < 100)len += 2;
        else if(i < 1000)len += 3;
        else if(i < 10000)len += 4;
        else if(i < 100000)len += 5;
        else if(i < 1000000)len += 6;
    }
    printf("%d\n", c(1) * c(10) * c(100) * c(1000) * c(10000) * c(100000) * c(1000000));
}

答案：210

PE41

从长度为9的排列开始，一直向下尝试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int p[] = {7, 6, 5, 4, 3, 2, 1};
bool isP(int x){
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0)
            return false;
    return true;
}
void solve(){
    while(prev_permutation(p, p + 7)){
        printf("x");
        int x = 0;
        for(int i = 0; i < 7; ++i)
            x = x * 10 + p[i];
        if(isP(x))break ;
    }
    for(int i = 0; i < 7; ++i)
        printf("%d", p[i]);
}

答案：7652413

PE42

字符串题。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int seq[10005], ans = 0;
char s[16];
void solve(){
    for(int i = 1; i <= 10000; ++i)
        seq[i - 1] = i * (i + 1) >> 1;
    for(; ; ){
        char c = getchar();
        if(c == EOF)break;
        int i = 0, sum = 0;
        while((c = getchar()) != '"')
            s[i++] = c, sum += c - 'A' + 1;
        s[i] = '\0';
        getchar();
        if(*lower_bound(seq, seq + 10000, sum) == sum)
            ans++;
    }
    printf("%d\n", ans);
}

答案：162

PE43

枚举排列即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int p[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int pr[] = {2, 3, 5, 7, 11, 13, 17};
ll ans = 0;
void solve(){
    do{
        int flag = 1;
        for(int i = 1; i < 8; ++i){
            int j = p[i] * 100 + p[i + 1] * 10 + p[i + 2];
            if(j % pr[i - 1] != 0){
                flag = 0;
                break;
            }
        }
        if(flag){
            ll x = 0;
            for(int i = 0; i < 10; ++i)
                x = x * 10 + p[i];
            ans += 1ll * x;
        }
    }while(next_permutation(p, p + 10));
    printf("%lld\n", ans);
}

答案：16695334890

PE44

枚举。
但是数据有一点吓人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll seq[40005];
void solve(){
    for(ll i = 1; i <= 40000; ++i)
        seq[i - 1] = i * (3 * i - 1) >> 1;
    int i;
    for(i = 0; i < 40000; ++i){
        int flag = 0;
        for(int j = 0; j < 40000; ++j){
            ll sum = seq[i] + seq[j];
            int index = lower_bound(seq, seq + 40000, sum) - seq;
            if(index == 40000)
                break;
            if(seq[index] == sum){
                index = lower_bound(seq, seq + 40000, sum + seq[j]) - seq;
                if(index < 40000 && seq[index] == sum + seq[j]){
                    flag = 1;
                    break;
                }
            }
        }
        if(flag)break ;
    }
    printf("%lld\n", seq[i]);
}

答案：5482660

PE45

枚举即可。
三角形数有点大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll sqr(ll x){
    ll r = (ll)floor(sqrt(x) + 0.5);
    if(r * r != x)
        return -1;
    return r;
}
void solve(){
    ll n;
    for(n = 286; n < 1000000; ++n){
        ll t = n * (n + 1) >> 1;
        ll a = sqr(1 + 8 * t), b = sqr(1 + 24 * t);
        if(a > 0 && (1 + a) % 4 == 0 && b > 0 && (1 + b) % 6 == 0)
            break;
    }
    printf("%lld\n", n);
}

答案：1533776805

PE46

枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int prime[100005], tot = 0;
bool vis[1000005] = {0};
bool isP(int x){
    if(x <= 1)return false;
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0)
            return false;
    return true;
}
bool isQ(int x){
    int d = (int)floor(sqrt(x) + 0.5);
    return d * d == x;
}
void getP(){
    for(int i = 2; i <= 1000000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 1000000; j += i)
                vis[j] = 1;
            prime[tot++] = i;
        }
}
void solve(){
    int ans;
    getP();
    for(int i = 35; ; i += 2){
        if(isP(i))continue ;
        int flag = 0;
        for(int j = 1; j < tot && i - prime[j] > 0; ++j)
            if(isQ((i - prime[j]) >> 1)){
                flag = 1;
                break ;
            }
        if(!flag){
            ans = i;
            break;
        }
    }
    printf("%d\n", ans);
}

答案：5777

PE47

找质因数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int get(int x){
    int cnt = 0, t = x;
    for(int i = 2; i * i <= x; ++i){
        if(t % i == 0){
            while(t % i == 0)
                t /= i;
            cnt++;
        }
        if(t == 1)break;
    }
    if(t != 1)cnt++;
    return cnt;
}
void solve(){
    bool b1 = 0, b2 = 0, b3 = 0, b4 = 0;
    int i;
    for(i = 6; ; ++i){
        if(get(i) == 4)
            b4 = 1;
        if(b1 && b2 && b3 && b4)
            break;
        b1 = b2, b2 = b3, b3 = b4, b4 = 0;
    }
    printf("%d\n", i - 3);
}

答案：134043

PE48

大力python
答案：9110846700

PE49

枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
bool vis[10005] = {0};
char s1[10], s2[10];
void getP(){
    for(int i = 2; i <= 10000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 10000; j += i)
                vis[j] = 1;
        }
}
bool cmp(int x, int y){
    sprintf(s1, "%d", x);
    sprintf(s2, "%d", y);
    sort(s1, s1 + 4);
    sort(s2, s2 + 4);
    return strcmp(s1, s2) == 0;
}
void solve(){
    getP();
    int ans1 = 0, ans2 = 0;
    for(int i = 1489; i < 10000; i += 2){
        if(vis[i])continue;
        for(int j = 2; i + j + j < 10000; ++j){
            if(vis[i + j] || vis[i + j + j])
                continue;
            if(!cmp(i, i + j) || !cmp(i, i + j + j))
                continue;
            ans1 = i, ans2 = j;
        }
        if(ans1)break;
    }
    printf("%d%d%d\n", ans1, ans1 + ans2, ans1 + 2 * ans2);
}

答案：296962999629

PE50

用前缀和枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int prime[100005], tot = 0, sum[100005] = {0};
bool vis[1000005] = {0};
void getP(){
    for(int i = 2; i <= 1000000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 1000000; j += i)
                vis[j] = 1;
            prime[++tot] = i;
        }
}
void solve(){
    getP();
    for(int i = 1; i <= 9592; ++i)
        sum[i] = sum[i - 1] + prime[i];
    int ans = 0;
    for(int i = 547; i >= 0; --i){
        for(int j = i; sum[j] - sum[j - i] < 1000000; ++j)
            if(!vis[sum[j] - sum[j - i]]){
                ans = sum[j] - sum[j - i];
                break ;
            }
        if(ans)break ;
    }
    printf("%d\n", ans);
}

答案：997651

PE51

千万看清楚题目！替换的数字一开始就需要相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
char s[10];
bool vis[1000005] = {0};
int yq[6], i;
void getP(){
    for(int i = 2; i <= 1000000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 1000000; j += i)
                vis[j] = 1;
        }
}
bool change(){
    sprintf(s, "%d", i);
    int cnt = 0, lst = -1;
    for(int i = 0; i < 5; ++i)
        if(yq[i]){
            if(lst < 0)lst = s[i] - '0';
            else if(lst > 2 || lst != s[i] - '0')return false;
        }
    for(int i = lst; i < 10; ++i){
        for(int j = 0; j < 5; ++j)
            if(yq[j])
                s[j] = i + '0';
        if(!vis[atoi(s)])
            cnt++;
    }
    return cnt == 8;
}
bool get(int d){
    if(d == 5){
        if(change())
            return true;
        return false;
    }
    yq[d] = 0;
    if(get(d + 1))return true;
    yq[d] = 1;
    if(get(d + 1))return true;
    return false;
}
void solve(){
    getP();
    for(i = 100001; i < 1000000; i += 2){
        if(i % 5 == 0 || vis[i])continue;
        if(get(0))
            break ;
    }
    printf("%d\n", i);
}

答案：121313

PE52

居然真的是142857。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int pp[8];
void solve(){
    int i;
    for(i = 1; i <= 1000000; ++i){
        for(int j = 1; j <= 6; ++j){
            pp[j] = 0;
            for(int t = i * j; t; t /= 10)
                pp[j] |= (1 << (t % 10));
        }
        int flag = 1;
        for(int j = 2; j <= 6; ++j)
            if(pp[j - 1] != pp[j]){
                flag = 0;
                break;
            }
        if(flag)break ;
    }
    printf("%d\n", i);
}

答案：142857

PE53

递推即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int dat[105][105] = {0};
void solve(){
    dat[1][0] = dat[1][1] = 1;
    int ans = 0;
    for(int i = 2; i <= 100; ++i){
        dat[i][0] = 1;
        for(int j = 1; j <= 100; ++j){
            if(dat[i - 1][j] + dat[i - 1][j - 1] > 1000000)
                dat[i][j] = 1000001, ans++;
            else 
                dat[i][j] = dat[i - 1][j] + dat[i - 1][j - 1];
        }
    }
    printf("%d\n", ans);
}

答案：4075

PE54

这就是个模拟题
和数学有毛关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
int p[2][6][2], ans = 0;
int tab[128];
int cnt[2][5], vcnt[2][19];
void init(){
    char cd[4];
    for(int o = 0; o < 2; ++o){
        for(int i = 0; i < 5; ++i){
            scanf("%s", cd);
            p[o][i][1] = tab[cd[1]];
            if(cd[0] == 'T')
                p[o][i][0] = 9;
            if(cd[0] == 'J')
                p[o][i][0] = 10;
            if(cd[0] == 'Q')
                p[o][i][0] = 11;
            if(cd[0] == 'K')
                p[o][i][0] = 12;
            if(cd[0] == 'A')
                p[o][i][0] = 13;
            if(isdigit(cd[0]))
                p[o][i][0] = cd[0] - '0' - 1;
        }
    }
    memset(cnt, 0, sizeof(cnt));
    memset(vcnt, 0, sizeof(vcnt));
}
int getRank(int o){
    for(int i = 0; i < 5; ++i)
        cnt[o][p[o][i][1]]++,
        vcnt[o][p[o][i][0]]++;
    
    int flag1 = 0, flag2 = 0, flag3 = 0;
    for(int i = 0; i < 4; ++i)
        if(cnt[o][i] == 5){
            flag1 = 1;
            if(vcnt[o][9] && vcnt[o][10] && vcnt[o][11] && vcnt[o][12] && vcnt[o][13])
                return 10;
            else{
                for(int j = 1; j < 9; ++j)
                    if(vcnt[o][j] && vcnt[o][j + 1] && vcnt[o][j + 2] && vcnt[o][j + 3] && vcnt[o][j + 4])
                        return 9;
            }
        }
    
    for(int i = 1; i <= 13; ++i)
        if(vcnt[o][i] == 4)
            return 8;
        else if(vcnt[o][i] == 3){
            flag2 = 1;
            for(int j = 1; j <= 13; ++j){
                if(j == i)continue;
                if(vcnt[o][j] == 2)
                    return 7;
            }
        }else if(vcnt[o][i] == 2)
            flag3++;
    
    if(flag1)return 6;
    for(int j = 1; j <= 9; ++j)
        if(vcnt[o][j] && vcnt[o][j + 1] && vcnt[o][j + 2] && vcnt[o][j + 3] && vcnt[o][j + 4])
            return 5;
    if(flag2)return 4;

    if(flag3 == 2)return 3;
    else if(flag3 == 1)return 2;

    return 1;
}
bool judge1(int lim){
    int maxi[2];
    for(int i = 0; i < 2; ++i)
        for(int j = 13; j >= 1; --j){
            if(vcnt[i][j] == lim){
                maxi[i] = j;
                break;
            }
        }
    return maxi[0] > maxi[1]; 
}
bool judge1(int lim, int lf){
    int maxi[2];
    for(int i = 0; i < 2; ++i)
        for(int j = 13; j >= 1; --j){
            if(vcnt[i][j] == lim){
                maxi[i] = j;
                break;
            }
        }
    if(maxi[0] == maxi[1])
        return judge1(lf);
    else 
        return maxi[0] > maxi[1];
}
bool judge2(){
    for(int j = 13; j >= 1; --j){
        if(vcnt[0][j] > vcnt[1][j])
            return true;
        else if(vcnt[0][j] < vcnt[1][j])
            return false;
    }
}
bool judge3(){
    int maxi[2];
    for(int i = 0; i < 2; ++i)
        for(int j = 13; j >= 1; --j){
            if(vcnt[i][j] == 3){
                maxi[i] = j;
                break;
            }
        }
    if(maxi[0] == maxi[1]){
        maxi[0] = maxi[1] = 0;
        for(int j = 13; j >= 1; --j){
            if(vcnt[0][j] == 1){
                if(maxi[0])maxi[1] = j;
                else maxi[0] = j;
            }
        }
        for(int j = 13; j >= 1; --j){
            if(vcnt[1][j] == 1){
                if(maxi[0] > j)
                    return true;
                else if(maxi[0] < j)
                    return false;
                else{
                    for(--j; j >= 1; --j)
                        if(vcnt[1][j] == 1)
                            return maxi[1] > j;
                }
            }
        }
    }else 
        return maxi[0] > maxi[1];
}
bool judge4(){
    int maxi[2];
    for(int i = 0; i < 2; ++i)
        for(int j = 13; j >= 1; --j){
            if(vcnt[i][j] == 2){
                maxi[i] = j;
                break;
            }
        }
    if(maxi[0] == maxi[1]){
        int maxii = maxi[0];
        for(int i = maxii - 1; i >= 1; ++i)
            if(vcnt[0][i] == 2){
                if(vcnt[1][i] == 2){
                    for(int j = 13; j >= 1; --j)
                        if(vcnt[0][j] == 1 || vcnt[1][j] == 1)
                            return vcnt[0][j] > vcnt[1][j];
                }else return true;
            }else if(vcnt[1][i] == 2)
                return false;
    }else 
        return maxi[0] > maxi[1];
}
bool judge5(){
    int maxi[2];
    for(int i = 0; i < 2; ++i)
        for(int j = 13; j >= 1; --j){
            if(vcnt[i][j] == 2){
                maxi[i] = j;
                break;
            }
        }
    if(maxi[0] == maxi[1]){
        for(int j = 13; j >= 1; --j){
            if(vcnt[0][j] == 1){
                if(vcnt[1][j] == 1){
                    for(--j; j >= 1; --j){
                        if(vcnt[0][j] == 1){
                            if(vcnt[1][j] == 1){
                                for(--j; j >= 1; --j){
                                    if(vcnt[0][j] == 1)return true;
                                    else if(vcnt[1][j] == 1)return false;
                                }
                            }else return true;
                        }else if(vcnt[1][j] == 1)
                            return false;
                        }
                }else return true;
            }else if(vcnt[1][j] == 1)
                return false;
        }
    }else 
        return maxi[0] > maxi[1];
}
void solve(){
    int r1 = getRank(0), r2 = getRank(1);
    if(r1 > r2)ans++;
    else if(r1 == r2){
        int flag = 0;
        if(r1 == 9 || r1 == 5)
            flag = judge1(1);
        if(r1 == 8)
            flag = judge1(4, 1);
        if(r1 == 7)
            flag = judge1(3);
        if(r1 == 6 || r1 == 1)
            flag = judge2();
        if(r1 == 4)
            flag = judge3();
        if(r1 == 3)
            flag = judge4();
        if(r1 == 2)
            flag = judge5();
        if(flag)
            ans++;
    }
    printf("%d\n", ans);
}
int main(){
    freopen("a.in", "r", stdin);
    tab['C'] = 0,
    tab['D'] = 1,
    tab['H'] = 2,
    tab['S'] = 3;
    for(int i = 0; i < 1000; ++i){
        init();
        solve();
    }
    return 0;
}

答案：376

PE55

还是用python水过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ans = 0

def rev(x):
    s = str(x)
    return s[::-1]

def judge(x):
    s = str(x)
    l = len(s)
    for i in range(0, l >> 1, 1):
        if s[i] != s[l - i - 1]:
            return 0
    return 1

for i in range(5, 10000, 1):
    x = i
    flag = 0
    for j in range(1, 50, 1):
        x += string.atoi(rev(x))
        if judge(x):
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

答案：249

PE56

用python水过

1
2
3
4
5
6
7
8
9
10
11
12
13
ans = 0

for i in range(1, 100, 1):
    for j in range(1, 100, 1):
        x = i ** j
        sum = 0
        while x > 0:
            sum += x % 10
            x /= 10
        if sum > ans:
            ans = sum

print(ans)

答案：972

PE57

用python水过
答案：153

PE58

相当于PE28的加强版。
数据很大！很大！不能模拟！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isP(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0)
            return false;
    }
    return true;
}
void solve(){
    int d, cnt = 0, cur = 1;
    for(d = 1; ; ++d){
        for(int i = 0; i < 4; ++i){
            cur += d << 1;
            if(isP(cur))
                cnt++;
        }
        double p = 1.0 * cnt / (4 * d + 1);
        if(p < 0.1)
            break;
    }
    printf("%d\n", d << 1 | 1);
}

答案：26241

PE59

用了一个剪枝就ok了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int s[100005], n = 0, ss[100005];
void init(){
    while(scanf("%d,", &s[n]) == 1)
        n++;
}
/*
void solve(){
    int cc[4];
	for(int i = 0; i < 26; ++i)
        for(int j = 0; j < 26; ++j)
            for(int k = 0; k < 26; ++k){
                cc[0] = i + 'a', cc[1] = j + 'a', cc[2] = k + 'a';
                int flag = 0;
                for(int t = 0; t < n; ++t){
                    ss[t] = (s[t] ^ cc[t % 3]);
                    if(ss[t] == '`' || ss[t] == '|'){
                        flag = 1;
                        break;
                    }
                }
                if(!flag){
                    for(int t = 0; t < n; ++t)
                        printf("%c", ss[t]);
                    printf("\n%c%c%c\n", cc[0], cc[1], cc[2]);
                }
            }
}*/
void solve(){
    int cc[] = {'g', 'o', 'd'}, ans = 0;
    for(int i = 0; i < n; ++i)
        ans += (s[i] ^ cc[i % 3]);
    printf("%d\n", ans);
}

答案：107359（密钥：god）

PE60

采用一定的枚举策略即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool vis[10005] = {0};
int prime[10005], tot = 2;
int ans = INF, c[10];
set<int> st[10005];
int getL(int x){
    if(x < 10)return 10;
    if(x < 100)return 100;
    if(x < 1000)return 1000;
    if(x < 10000)return 10000;
}
bool isP(int x){
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0)
            return false;
    return true;
}
bool judge(int x1, int x2){
    if(st[x1].count(x2))
        return false;
    int l1 = getL(x1), l2 = getL(x2);
    if(!isP(x1 + l1 * x2) || !isP(x2 + l2 * x1)){
        st[x1].insert(x2);
        return false;
    }
    return true;
}
void getP(){
    for(int i = 2; i <= 10000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 10000; j += i)
                vis[j] = 1;
        }
    prime[0] = 3, prime[1] = 7;
    for(int i = 11; i < 10000; i += 2)
        if(!vis[i])
            prime[tot++] = i;
}
void getC(int index, int left, int sum){
    c[left] = prime[index];
    for(int i = left + 1; i < 5; ++i)
        if(!judge(c[i], prime[index]))
            return ;
    if(sum >= ans)return ;
    if(left == 0){
        ans = sum;
        return ;
    }
    for(int i = index + 1; i <= tot - left; ++i)
        getC(i, left - 1, sum + prime[i]);
}
void solve(){
    getP();
    for(int i = 0; i <= tot - 5; ++i)
        getC(i, 4, prime[i]);
    printf("%d\n", ans);
}