PE 111 Primes with runs （数位dp）-蒲公英云

PE 111 Primes with runs （数位dp）

Primes with runs

Problem 111

Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d	M(4, d)	N(4, d)	S(4, d)
0	2	13	67061
1	3	9	22275
2	3	1	2221
3	3	12	46214
4	3	2	8888
5	3	1	5557
6	3	1	6661
7	3	9	57863
8	3	1	8887
9	3	7	48073

For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).

题意：

有重复数字的素数

考虑一个有重复数字的4位素数，显然这4个数字不能全都一样：1111被11整除，2222被22整除，依此类推；但是，有9个4位素数包含有三个一：

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

我们记M(n, d)是n位素数中数字d重复出现的最多次数，N(n, d)是这类素数的个数，而S(n, d)是这类素数的和。

因此M(4, 1) = 3是4位素数中数字1重复出现的最多次数，有N(4, 1) = 9个这类素数，而它们的和是S(4, 1) = 22275。还能得出，对于d = 0，在4位素数中最多重复出现M(4, 0) = 2次，但是有N(4, 0) = 13个这类素数。

同样地，我们可以得到4位素数的如下结果。

数字d	M(4, d)	N(4, d)	S(4, d)
0	2	13	67061
1	3	9	22275
2	3	1	2221
3	3	12	46214
4	3	2	8888
5	3	1	5557
6	3	1	6661
7	3	9	57863
8	3	1	8887
9	3	7	48073

对于d = 0至9，所有S(4, d)的和为273700。

求所有S(10, d)的和。

题解：暴力也行，大概1min，数位dp更快，100ms。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll>s;
int isPrime(ll n) 
{
        for(ll i=2;i<=(ll)sqrt(n);i++){
            if(n%i==0)return 0;
        }
        return 1;
}
void gao(ll num, int pos, int len, int repeat_Dig, int num_repeat_Dig, set<ll>& s)
{
    if(len - pos < num_repeat_Dig) return;
    if(pos == len)
    {
        if(isPrime(num))
        {
            s.insert(num);
        }
        return ;
    }
    if(num_repeat_Dig != 0 && !(repeat_Dig == 0 && pos == 0))
    {
        gao(num * 10 + repeat_Dig, pos + 1, len, repeat_Dig, num_repeat_Dig - 1, s);
    }
    for(int i = pos == 0 ? 1 : 0; i <= 9; i++)
    {
        if(i == repeat_Dig) continue;
        gao(num * 10 + i, pos + 1, len, repeat_Dig, num_repeat_Dig, s);
    }
    return ;
}
int main() 
{
    int n; 
    cin>>n; //位数 
    ll ans = 0;
    for(int dig = 0; dig <= 9; dig++) //数字dig重复次数最多的数 
    {
        s.clear();
        for(int num_repeat_Dig = n; num_repeat_Dig >= 1; num_repeat_Dig--) 
        { 
            gao(0, 0, n, dig, num_repeat_Dig, s);
            if(!s.empty())
            {
                ll sum = 0;
                for(set<ll>::iterator it=s.begin();it !=s.end();++it)
                {
                    sum += *it;
                    //cout<<*it<<endl;
                }
                cout<<sum<<endl;
                ans += sum;
                break;
            }
        }
    }
    cout<<"ans="<<ans<<endl;
    return 0;
}