Problem 43 Sub-string divisibility （暴力...）

Bertha 。 2022-07-15 02:42 103阅读 0赞

## Sub-string divisibility ##

### Problem 43 ###

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let *d*1 be the 1st digit, *d*2 be the 2nd digit, and so on. In this way, we note the following:

*  *d*2*d*3*d*4=406 is divisible by 2
 *  *d*3*d*4*d*5=063 is divisible by 3
 *  *d*4*d*5*d*6=635 is divisible by 5
 *  *d*5*d*6*d*7=357 is divisible by 7
 *  *d*6*d*7*d*8=572 is divisible by 11
 *  *d*7*d*8*d*9=728 is divisible by 13
 *  *d*8*d*9*d*10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td> 
        <div style="text-align:right"> 
         <span style="font-size:18px">Answer:</span> 
        </div> </td> 
       <td><strong><span style="font-size:18px">16695334890</span></strong></td> 
      </tr> 
      <tr> 
       <td colspan="2"><span style="color:rgb(153,153,153)"><span style="font-size:18px">Completed on Sun, 30 Oct 2016, 07:48</span></span></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
 </tbody> 
</table>

题解：无脑暴力....

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	long long a[10]={0,1,2,3,4,5,6,7,8,9};
    	int ans=0;
    	unsigned long long sum=0;
    	do
    	{
    		if((a[1]*100+a[2]*10+a[3])%2==0)
    		{
    			if((a[2]*100+a[3]*10+a[4])%3==0)
    			{
    				if((a[3]*100+a[4]*10+a[5])%5==0)
    				{
    					if((a[4]*100+a[5]*10+a[6])%7==0)
    					{
    						if((a[5]*100+a[6]*10+a[7])%11==0)
    						{
    							if((a[6]*100+a[7]*10+a[8])%13==0)
    							{
    								if((a[7]*100+a[8]*10+a[9])%17==0)
    								{
    									ans++;
    									sum+=(a[0]*1000000000+a[1]*100000000+a[2]*10000000+a[3]*1000000);
    									sum+=(a[4]*100000+a[5]*10000+a[6]*1000+a[7]*100+a[8]*10+a[9]);
    									cout<<a[0]<<a[1]<<a[2]<<a[3]<<a[4]<<a[5]<<a[6]<<a[7]<<a[8]<<a[9]<<endl;
    									
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    		
    	}while(next_permutation(a,a+10));
    	cout<<ans<<endl;
    	cout<<sum<<endl;
    	return 0;
    }