题目
对于任意一个至少两位的正整数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<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#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<<s[i]<<' '; 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<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#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<<s[i]<<' '; 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;
}