题目

对于任意一个至少两位的正整数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]中有多少个数是幸运数。

输入格式

输入两行，每行一个数。第一行是A，第二行表示B。

输出格式

输出[A,B]中有多少个数是幸运数。

输入样例

1

9

输出样例

1

提示

数据范围：

对30%数据，B≤10000。

对100%数据，0<A≤B≤1,000,000,000。

题解

这解法。。无敌了

分块大法好

将区间分\(\sqrt{N}\)块，打表出每一块的答案【暴力打个1min就差不多了】

询问时\(O(\sqrt{N})\)统计，最后一块\(O(\sqrt{N}*10)\)暴力计算

这暴力太优美了

打表程序【记得先调一下再打。。别打半天打出个错的表】

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
         
          <<' '; puts("");using namespace std;const int maxn = 32000,maxm = 1000000001,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();} return out * flag;}int cal(int n){ int x,p; while (n / 10){ x = n; p = 1; n = 0; while (x / 10) n += p * abs((x % 10) - (x / 10 % 10)),p *= 10,x /= 10; } return n;}int main(){ freopen("biao.txt","w",stdout); printf("{"); int B = (int)sqrt(1000000000),now = 0,ans = 0; for (int i = 1; i <= 1000000000; i++){ if (i / B > now) now = i / B,printf("%d,",ans),ans = 0; if (cal(i) == 7) ans++; } printf("}"); /*while (true){ int n = read(); printf("%d\n",cal(n)); }*/ return 0;}
         
        
       
      
     
    

AC程序【省略打表部分】

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
         
          <<' '; puts("");using namespace std;const int maxn = 400005,maxm = 100005,INF = 1000000000;int biao[]={/*此处过于壮观，就略去了*/};int L,R;int cal(int n){ int x,p; while (n / 10){ x = n; p = 1; n = 0; while (x / 10) n += p * abs((x % 10) - (x / 10 % 10)),p *= 10,x /= 10; } return n;}int main(){ cin>>L>>R; L--; int ans = 0,T = (int)sqrt(1000000000),bl = L / T,br = R / T; for (int i = bl; i < br; i++) ans += biao[i]; for (int i = br * T; i <= R; i++) ans += (cal(i) == 7); for (int i = bl * T; i <= L; i++) ans -= (cal(i) == 7); printf("%d\n",ans); return 0;}