Luogu P1822 魔法指纹

题目描述

https://www.luogu.com.cn/problem/P1822

简要题意：定义 $magic(n)$ 等于将 $n$ 按十进制顺序写下来，依次对相邻两个数写下差的绝对值，得到的新数，例如 $magic(5913)=482$，对于一个大于等于 $10$ 的数字，我们不断进行 $magic$ 变换，最后一定可以得到一个小于 $10$ 的数字，如果一个数字 $n$ 可以通过不断进行 $magic$ 变换得到 $7$，那么我们称它为幸运数字，现在给定 $l,r$，求 $[l,r]$ 范围内有多少幸运数字

$1\le l\le r\le 10^9$

Solution

我们考虑判断一个数字是否是幸运数字大概需要 $O(\log_{10}^2n)$ 的时间，大概 $1s$ 只能做 $10^6$ 次判断

所以我们考虑分段打表，令块大小为 $10^6$，这样本地打表大概需要 $10min$，且表的大小只有不超过 $10k$

#include <iostream>
#include <vector>
using namespace std;

int f[] = { 0,2045,3089,3839,4196,4512,4828,5186,5935,6979,8453,9319,10363,10666,10886,11040,11155,11239,11364,11710,12637,13015,13573,14323,14544,14748,14902,15020,15154,15300,15682,15792,16062,16365,16722,16898,17102,17270,17398,17487,17562,17647,17773,18071,18292,18608,18784,19004,19172,19260,19329,19398,19486,19654,19874,20050,20366,20587,20885,21011,21096,21171,21260,21388,21556,21760,21936,22293,22596,22866,22977,23359,23504,23638,23756,23910,24114,24336,25085,25643,26021,26948,27295,27419,27503,27618,27772,27992,28295,29339,30205,32227,32981,33205,33276,33362,33477,33645,33943,34501,35975,36601,37159,37277,37358,37409,37442,37461,37491,37807,39268,40134,41178,41481,41701,41855,41970,42054,42179,42525,43452,43562,44120,44214,44435,44531,44608,44656,44688,44714,44774,44848,45118,45234,45300,45395,45599,45717,45800,45855,45884,45934,46060,46178,46255,46305,46381,46494,46662,46719,46762,46806,46894,47002,47081,47121,47162,47206,47297,47395,47480,47521,47610,47679,47760,47794,47817,47847,47868,47948,48015,48151,48296,48370,48434,48485,48506,48528,48552,48587,48640,49129,49476,49551,49612,49663,49687,49700,49728,49900,49979,51122,51876,51923,51968,52019,52055,52070,52090,52319,53243,53483,53723,54021,54139,54208,54259,54287,54330,54393,54978,55844,56172,56475,56588,56665,56716,56751,56776,56838,57213,57591,58149,58899,59120,59324,59478,59596,59730,59876,60258,60325,60519,60822,60906,61082,61178,61259,61308,61340,61365,61412,61510,61808,61934,62003,62098,62318,62426,62478,62516,62559,62616,62784,62897,62973,63023,63100,63218,63344,63394,63442,63511,63639,63757,63817,63857,63891,63920,64016,64090,64246,64343,64477,64553,64630,64664,64691,64714,64740,64795,64957,65150,65274,65328,65397,65448,65471,65494,65529,65566,65877,66192,66416,66451,66509,66560,66582,66610,66682,66959,66984,67062,67180,67348,67413,67471,67506,67533,67547,67561,67943,68035,68151,68371,68472,68541,68594,68627,68666,68698,68808,69366,69460,69681,69777,69854,69902,69934,69960,70020,70130,70400,70703,71060,71236,71440,71608,71736,71825,71900,71934,72017,72135,72356,72420,72596,72709,72818,72860,72887,72925,72977,73085,73305,73400,73469,73595,73893,73991,74038,74073,74127,74196,74364,74460,74536,74595,74660,74854,74964,75015,75081,75155,75273,75374,75434,75478,75508,75555,75693,75725,75785,75860,75944,76009,76086,76138,76159,76184,76217,76241,76282,76329,76400,76452,76521,76577,76611,76646,76662,76685,76732,76823,76941,77056,77108,77153,77188,77204,77219,77389,77453,77518,77631,77785,77850,77911,77943,77975,77995,78373,78613,78692,78818,79022,79123,79187,79233,79260,79314,79381,79575,79878,79962,80138,80234,80315,80364,80396,80421,80506,80632,80930,81151,81467,81643,81863,82031,82119,82188,82215,82257,82366,82479,82655,82719,82940,83058,83141,83175,83204,83259,83342,83460,83664,83759,83825,83941,84211,84285,84326,84375,84453,84529,84683,84779,84856,84889,84967,85077,85100,85146,85195,85249,85364,85465,85544,85573,85596,85648,85663,85685,85738,85773,85859,85924,86005,86057,86083,86095,86107,86133,86185,86266,86331,86417,86452,86505,86527,86542,86594,86617,86646,86725,86826,86941,86995,87044,87090,87113,87223,87301,87334,87411,87507,87661,87737,87815,87864,87905,87979,88249,88365,88431,88526,88730,88848,88931,88986,89015,89049,89132,89250,89471,89535,89711,89824,89933,89975,90002,90071,90159,90327,90547,90723,91039,91260,91558,91684,91769,91794,91826,91875,91956,92052,92228,92312,92615,92809,92876,92930,92957,93003,93067,93168,93372,93498,93577,93817,94195,94215,94247,94279,94340,94405,94559,94672,94737,94801,94971,94986,95002,95037,95082,95134,95249,95367,95458,95505,95528,95544,95579,95613,95669,95738,95790,95861,95908,95949,95973,96006,96031,96052,96104,96181,96246,96330,96405,96465,96497,96635,96682,96712,96756,96816,96917,97035,97109,97175,97226,97336,97530,97595,97654,97730,97826,97994,98063,98117,98152,98199,98297,98595,98721,98790,98885,99105,99213,99265,99303,99330,99372,99481,99594,99770,99834,100055,100173,100256,100290,100365,100454,100582,100750,100954,101130,101487,101790,102060,102170,102230,102256,102288,102336,102413,102509,102730,102824,103382,103492,103524,103563,103596,103649,103718,103819,104039,104155,104247,104629,104643,104657,104684,104719,104777,104842,105010,105128,105206,105232,105508,105580,105608,105630,105681,105739,105775,105999,106314,106624,106661,106696,106719,106742,106793,106862,106916,107041,107234,107395,107450,107476,107499,107526,107560,107637,107713,107847,107945,108100,108174,108270,108299,108333,108373,108433,108551,108679,108748,108796,108846,108972,109090,109167,109217,109293,109406,109574,109631,109674,109712,109764,109872,110092,110187,110256,110382,110680,110778,110825,110850,110882,110931,111012,111108,111284,111368,111671,111865,111933,112315,112460,112594,112712,112866,113070,113292,114041,114599,114978,115352,115414,115439,115474,115525,115602,115715,116019,116346,117213,117797,117860,117903,117931,117982,118051,118169,118467,118708,118947,119871,120100,120120,120135,120171,120222,120267,120314,121068,122211,122290,122462,122490,122503,122527,122578,122639,122715,123061,123550,123603,123638,123662,123684,123705,123756,123820,123894,124039,124175,124242,124322,124343,124373,124396,124430,124511,124580,124669,124710,124795,124893,124984,125028,125069,125109,125188,125296,125384,125428,125471,125528,125696,125809,125885,125935,126012,126130,126256,126306,126335,126390,126473,126591,126795,126890,126956,127072,127342,127416,127476,127502,127534,127582,127659,127755,127976,128070,128628,128738,129665,130012,130136,130220,130335,130489,130709,131012,132056,132922,134383,134699,134729,134748,134781,134832,134913,135031,135589,136215,139782,142039,142127,142133,142153,142186,142221,142275,142589,144611,144982,145988,146122,146131,146140,146176,146229,146279,146471,147398,147455,147527,147611,147625,147636,147660,147708,147786,147884,148266,148312,148353,148376,148394,148403,148424,148480,148563,148632,148707,148757,148840,148892,148919,148940,148963,149015,149124,149181,149250,149294,149382,149490,149569,149609,149650,149694,149785,149883,149968,150003,150057,150126,150294,150390,150466,150525,150590,150784,150894,150948,150975,151021,151085,151186,151390,151516,151595,151835,152214,152588,152650,152675,152710,152761,152838,152951,153255,153582,154448,156470,157224,157448,157519,157605,157720,157888,158186,158744,160218 };

const int N = 1000000;

int l, r;

int solve(int x) {
    vector<int> a; int res = 0; 
    while (x) a.push_back(x % 10), x /= 10;
    for (int i = a.size() - 1; i; --i) res = res * 10 + abs(a[i] - a[i - 1]);
    return res;
}

inline int check(int x) {
    while (x > 9) x = solve(x);
    return x == 7; 
}

int calc(int n) {
    int k = n / N, r = n % N, res = f[k];
    for (int i = 1; i <= r; ++i) res += check(k * N + i);
    return res;
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << "\n";
    return 0;
}