Description
题目描述
对于任意一个至少两位的正整数n，按如下方式定义magic(n)：将n按十进制顺序写下来，依次对相邻两个数写下差的绝对值。这样，得到了一个新数，去掉前导0，则定义为magic(n)。若n为一位数，则magic(n)=n。
例如：magic(5913)=482，magic(1198)=081=81，magic(666)=00=0。
对任意一个数n，序列n，magic(n)，magic(magic(n))，…迟早会变成一个一位数。最后的这个值称为数n的magic指纹。
例如，对于n=5913，我们得到序列：5913，482，46，2。所以5913的magic指纹为2。
若一个数的magic指纹为7，则认为这个数是个幸运数。
现在，给定A，B，计算出[A,B]中有多少个数是幸运数。
输入格式
输入两行，每行一个数。第一行是A，第二行表示B。
输出格式
输出[A,B]中有多少个数是幸运数。
Solution
显然打表是一个好的选择，但数据范围太大开不了数组
考虑到每个数的判定是独立的，我们可以将打表与分块结合，大段打表，小段暴力
Code
#include <cstdio> #include <cstdlib> using namespace std; const int d[1010]={/*打表获取,i*T~(i+1)*T-1为一段*/}; int a,b,ans,y,wz,z,dd[20]; int T=1000000; int magic(int x) { while(x>=10) { y=0,wz=0,z=1; while(x) dd[wz++]=x%10,x/=10; for(int i=0;i<wz-1;i++) y+=abs(dd[i+1]-dd[i])*z,z*=10; x=y; } return x; } int main() { scanf("%d%d",&a,&b); if(magic(b)==7) ans++; b--; int x=a/T,y=b/T; ans+=d[y]-d[x]; for(int i=a;i<(x+1)*T;i++) if(magic(i)==7) ans++; for(int i=b+1;i<(y+1)*T;i++) if(magic(i)==7) ans--; printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/hsez-cyx/p/12254714.html