PE 111 Primes with runs （数位dp）

旧城等待， 2022-07-13 11:42 131阅读 0赞

## 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.

<table> 
 <tbody> 
 <tr> 
 <td>Digit,&nbsp;d</td> 
 <td>M(4,&nbsp;d)</td> 
 <td>N(4,&nbsp;d)</td> 
 <td>S(4,&nbsp;d)</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td>2</td> 
 <td>13</td> 
 <td>67061</td> 
 </tr> 
 <tr> 
 <td>1</td> 
 <td>3</td> 
 <td>9</td> 
 <td>22275</td> 
 </tr> 
 <tr> 
 <td>2</td> 
 <td>3</td> 
 <td>1</td> 
 <td>2221</td> 
 </tr> 
 <tr> 
 <td>3</td> 
 <td>3</td> 
 <td>12</td> 
 <td>46214</td> 
 </tr> 
 <tr> 
 <td>4</td> 
 <td>3</td> 
 <td>2</td> 
 <td>8888</td> 
 </tr> 
 <tr> 
 <td>5</td> 
 <td>3</td> 
 <td>1</td> 
 <td>5557</td> 
 </tr> 
 <tr> 
 <td>6</td> 
 <td>3</td> 
 <td>1</td> 
 <td>6661</td> 
 </tr> 
 <tr> 
 <td>7</td> 
 <td>3</td> 
 <td>9</td> 
 <td>57863</td> 
 </tr> 
 <tr> 
 <td>8</td> 
 <td>3</td> 
 <td>1</td> 
 <td>8887</td> 
 </tr> 
 <tr> 
 <td>9</td> 
 <td>3</td> 
 <td>7</td> 
 <td>48073</td> 
 </tr> 
 </tbody> 
</table>

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 = 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;
 }