Project Euler——Problem 32
原题与答案:
Problem 32
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
Answer:45228
分析与解答:
这个题目是求所有的满足条件的乘法表达式的积的和,题目中的条件是要求表达式中出现1到9这9个数字,每个有且只有一次。仔细分析一下去掉一些不可能的情况,首先是我们的表达式里面一共有9个数字,这样我们先考虑生成9的全排列,然后再加入乘号和等号,同时考虑到我们加入乘号和等号的情况总数为C(8,2)=28种,我们可以从这里排除掉一大堆不可能的情况。对于一个n位数和一个m位数的乘法,他们的积只可能是n+m或者是n+m-1位数,于是乎我们可以假设当被乘数小等于乘数的时候,我们得到的只可能有两种情况符合题意,即1位数*4位数=4位数或者是2位数*3位数=4位数,这样我们就将情况数从28种缩减到了2种,然后就是枚举计算的事情了,实际上满足条件的表达式非常少,因为积都是4位数,不会超过P(9,4)=3024个,但是实际算出来只有9个。我的程序源代码如下所示:
-
#include<stdio.h>
-
#include<string.h>
-
#include<algorithm>
-
int list[10],prod[3100],i,j,ans,s,t,u;
-
bool yet[10],first=true;
-
void check()
-
{
-
int i;
-
for (u=0,i=5;i<9;i++) u=u*10+list[i];
-
for (s=i=0;i<1;i++) s=s*10+list[i];
-
for (t=0,i=1;i<5;i++) t=t*10+list[i];
-
if (s&&t>=1000&&u>=1000&&s*t==u)
-
prod[++prod[0]]=u;
-
for (s=i=0;i<2;i++) s=s*10+list[i];
-
for (t=0,i=2;i<5;i++) t=t*10+list[i];
-
if (s>=10&&t>=100&&u>=1000&&s*t==u)
-
prod[++prod[0]]=u;
-
}
-
void calc(int pos)
-
{
-
if (pos==9) check();
-
else
-
for (list[pos]=1;list[pos]<=9;list[pos]++)
-
if (!yet[list[pos]])
-
{
-
yet[list[pos]]=true;
-
calc(pos+1);
-
yet[list[pos]]=false;
-
}
-
}
-
int main()
-
{
-
prod[0]=0;
-
memset(yet,false,sizeof(yet));
-
calc(0);
-
std::sort(prod+1,prod+prod[0]+1);
-
for (ans=0,i=j=1;;i=j)
-
{
-
ans+=prod[i];
-
while (j<=prod[0]&&prod[i]==prod[j])
-
j++;
-
if (j>prod[0]) break;
-
}
-
return 0;
-
}