首先假定已经找到abc符合题目条件。则我们假定a1,a2,a3...;b1,b2,b3...;c1,c2,c3...为abc各个位置上的数字,那么
a1 a2 a3
b1 b2 b3
+ c1 c2 c3
----------------
x1 x2 x3
又由digsum等式可知a1+b1+c1+...=x1+x2+x3。
那么我们根据竖式不难发现在每一位进行加法时不能够产生进位,否则将不满足digsum等式。
即a3+b3+c3=x3;a2+b2+c2=x2;a1+b1+c1=x1。
所以我们只需要求出x每一位有几种拆法,然后再相乘。
拆分方法我们可以借鉴高中隔板法:有Xi个小球要求分成三部分,有几种分法。
主要代码:
#include<bits/stdc++.h> using namespace std; int main(){ int a[15]={1,3,6,10,15,21,28,36,45,55}; //Xi个小球的分法 int t; cin>>t; while (t--){ int n; cin>>n; if (n==0){ //0需要特判 printf("%d\n",1); continue; } long long int sum=1; //longlongint避免溢出 while (n!=0){ //每一位方法数相乘 sum*=a[n%10]; n/=10; } cout<<sum<<endl; } return 0; }