Problem 38 Pandigital multiples （set + vector）

た入场券 2022-07-15 02:26 72阅读 0赞

## Pandigital multiples ##

### Problem 38 ###

Take the number 192 and multiply it by each of 1, 2, and 3:

> 192 × 1 = 192  
> 192 × 2 = 384  
> 192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

<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">932718654</span></strong></td> 
      </tr> 
      <tr> 
       <td colspan="2"><span style="color:rgb(153,153,153)"><span style="font-size:18px">Completed on Sat, 29 Oct 2016, 15:45</span></span></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
 </tbody> 
</table>

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    void split_digits(int n, vector<int>& v)
    { 
        int digits[12];
        int len = 0;
        while(n>0)
        {
            digits[len++] = n %10;
            n /= 10;
        }
     
        for(int i=len-1;i>=0;i--)  
        {
            v.push_back(digits[i]);
        }
    }
     
    void disp(int n){ cout<<n; }
     
    int main()
    {
        for(int x=1;x<10000;x++)
        {
            vector<int> s;
            int n = 0;    
            while(n<=9)
            {
            	n++;
                split_digits(n*x,s); //n*x 的各位数字加入到 vector<int>s中
                
                if (s.size() == 9)
                {
                    set<int> set_product(s.begin(),s.end()); //将vector中的数字保存到set集合中
                    if(set_product.size() == 9) //说明没有重复数字
                    {
                        //判断是否含有数字 0
                        set<int>::iterator it = set_product.find(0);
                        
                        if (it == set_product.end())  //不含数字 0
                        {
                            //满足条件,输出 
                            cout<<"x="<<x<<" n="<<n<<" ";
                            cout<<"乘积和为：";
                            for_each(s.begin(),s.end(),disp);
                            cout<<endl;
                        }
                    }
                }
                else if (s.size() > 9)
                {
                    break;  //下一个 x 
                }                
            }
            
        }
        return 0;
    }