[CQOI2016] 手机号码----分段打表

· · 题解

这题上来，直接想到分段打表。

分段打表是什么呢？

我用我理解的说一下吧！

对于一个递推 f_x=\sum_{i=x-a}^{x-1}v_{x,i}f_i+w_x。

让你求 f_n，其中 3\times 10^8\le n \le 10^{13}。

以上范围大约是分段打表能解决的。

我们设一个阈值 l，在程序外把 f_l,f_{l+1}\dots f_{l+a},f_{2l}\dots f_{2l+a},f_{3l}\dots f_{3l+a}\dots f_{kl}\dots f_{kl+a} 的值跑出来，放在程序里，储存在数组里。

其中 kl\le \max n。

对于要计算的 f_n 的时候，按原来的递推式递推。

但是递推起点为 f_{\lfloor \frac{n}{l} \rfloor \times l+a+1}。

这样空间复杂度 O(\dfrac{\max n}{l})，时间复杂度 O(l)，优化的方法和分块差不多。

首先，本题是个递推，式子为 f_x=f_{x-1}+c_x。

是个类似于前缀和的东东。

所以可以用 f_r-f_{l-1} 求区间 [l,r] 的答案。

其中 c_x 是个 bool 变量，用于表示是否满足电话号码。

本题数据范围为 10^{11}，可以分段打表。

下面是我打表的图片，整整打了 40 分钟，取的 l=10^8。

但是因为忽略了枚举位的常数所以后面重新取了 l=2\times 10^7。

打表代码如下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int t=2e7,n=1e10;
inline bool check(int x){//判断 
    int pre1=0,pre2=0;
    pre2=x%10,x/=10;
    pre1=x%10,x/=10;
    bool flag=0,f1=0,f2=0;
    if(pre1==4 || pre2==4) f1=1;
    if(pre1==8 || pre2==8) f2=1;
    while(x){
        int u=x%10;
        if(u==pre1 && pre1==pre2) flag=1;
        if(u==4) f1=1;if(u==8) f2=1;
        pre2=pre1,pre1=u,x/=10;
    }
    if(f1 && f2) return 0;
    return flag;
}
int ans=0;
signed main() {
    for(int i=n;i<n*10;i+=t){//分段枚举
        for(int j=max(n,i-t+1);j<=i;j++) if(check(j)) ans++;
        cout<<ans<<",";
    }
    system("pause");
    while(true);
    return 0;
}

::::info[AC 代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const signed t=2e7;
const int n=1e10;
const int a[]={1,7930813,8854865,9634708,10558760,11338603,12948366,13872418,14652261,15576313,16356156,17280208,18889971,19669814,20593866,21373709,22297761,23907524,24687367,25611419,26391262,27026896,27662530,28749236,29384869,29702687,30626739,31550791,33016345,33940397,34720240,35644292,36568344,37348187,38957950,39737793,40661845,41585897,42365740,43975503,44755346,45390980,46026613,46344431,46980065,48066771,48990823,49914875,50694718,51618770,53084324,54694087,55618139,56397982,57322034,58101877,73039449,87977021,100228776,115166348,127418103,128342155,129951918,130731761,131655813,132435656,133359708,134969471,135749314,136673366,137453209,138088843,138724477,139811183,140446816,140764634,141688686,142612738,144078292,145002344,145782187,146706239,147630291,148410134,150019897,150799740,151723792,152647844,153427687,155037450,155817293,156452927,157088560,157406378,158042012,159128718,160052770,160976822,161756665,162680717,164146271,165756034,166680086,167459929,168383981,169163824,170773587,171697639,172477482,173401534,174181377,175105429,183036241,183816084,184740136,185519979,186444031,188053794,188833637,189757689,190537532,191173166,191808800,192895506,193531139,193848957,194773009,195697061,197162615,198086667,198866510,199790562,200714614,201494457,203104220,
203884063,204808115,205732167,206512010,208121773,208901616,209537250,210172883,210490701,211126335,212213041,213137093,214061145,214840988,215765040,217230594,218840357,219764409,220544252,221468304,222248147,223857910,224781962,225561805,226485857,227265700,228189752,229799515,230579358,231503410,232283253,233207305,241138117,241917960,242842012,243621855,244257489,244893123,245979829,246615462,246933280,247857332,248781384,250246938,251170990,251950833,252874885,253798937,254578780,256188543,256968386,257892438,258816490,259596333,261206096,261985939,262621573,263257206,263575024,264210658,265297364,266221416,267145468,267925311,268849363,270314917,271401623,272037257,272672891,273308524,273626342,274713048,275348682,275984316,276619949,276937767,277573401,278660107,279295741,279931374,280249192,280884826,281971532,282607166,283242799,283560617,284196251,284831885,289932671,290568304,290886122,291521756,292157390,293244096,293879729,294197547,294833181,295468815,296104449,297191154,297508972,298144606,298780240,299415874,300502579,300820396,300820396,300820396,300820396,300820396,300820397,301456031,302091665,302727299,303362932,304131822,305741585,306665637,307445480,308369532,309149375,310759138,311683190,312463033,313387085,314166928,315090980,316700743,317480586,318404638,319184481,320108533,321718296,322498139,323422191,324202034,324837668,325473302,326560008,327195641,327513459,328437511,329361563,337148166,338072218,338852061,339776113,340700165,341480008,343089771,343869614,344793666,345717718,346497561,348107324,348887167,349522801,350158434,350476252,351111886,352198592,353122644,354046696,354826539,355750591,357216145,358825908,359749960,360529803,361453855,362233698,363843461,364767513,365547356,366471408,367251251,368175303,369785066,370564909,371488961,372268804,373192856,374802619,375582462,376506514,377286357,377921991,378557625,379644331,380279964,380597782,381521834,382445886,383911440,384835492,385615335,386539387,387463439,388243282,396174094,396953937,397877989,398802041,399581884,401191647,401971490,402607124,403242757,403560575,404196209,405282915,406206967,407131019,407910862,408834914,410300468,411910231,412834283,413614126,414538178,415318021,416927784,417851836,418631679,419555731,420335574,421259626,422869389,423649232,424573284,425353127,426277179,427886942,428666785,429590837,430370680,431006314,431641948,432728654,433364287,433682105,434606157,435530209,436995763,437919815,438699658,439623710,440547762,441327605,442937368,443717211,444641263,445565315,446345158,454275970,455055813,455691447,456327080,456644898,457280532,458367238,459291290,460215342,460995185,461919237,463384791,464471497,465107130,465424948,466060582,466696216,467782922,468418555,468736373,469372007,470007641,470643275,471729980,472047798,472683432,473319066,473954700,475041405,475359223,475994857,476630490,476630490,476630490,476630490,476630490,476630491,477266125,477901758,478670648,479306282,479941916,480577550,481213183,481531001,482617707,483253341,483888975,484524608,484842426,485929132,486564766,487200400,487836033,488153851,488789485,493890271,494525905,495161538,495479356,496114990,497201696,498811459,499735511,500515354,501439406,502219249,503829012,504753064,505532907,506456959,507236802,508160854,509770617,510550460,511474512,512254355,513178407,514788170,515568013,516492065,517271908,517907542,518543176,519629882,520265515,520583333,521507385,522431437,523896991,524821043,525600886,526524938,527448990,528228833,529838596,530618439,531542491,532466543,533246386,534856149,535635992,536271626,536907259,537225077,537860711,538947417,539871469,540795521,541575364,542499416,550286019,558216831,559140883,559920726,560844778,561624621,563234384,564158436,564938279,565862331,566642174,567566226,569175989,569955832,570879884,571659727,572583779,574193542,574973385,575897437,576677280,577312914,577948548,579035254,579670887,579988705,580912757,581836809,583302363,584226415,585006258,585930310,586854362,587634205,589243968,590023811,590947863,591871915,592651758,594261521,595041364,595676998,596312631,596630449,597266083,598352789,599276841,600200893,600980736,601904788,603370342,604980105,605904157,606684000,607608052,608387895,616318707,617242759,618022602,618946654,619726497,620650549,622260312,623040155,623964207,624744050,625668102,627277865,628057708,628981760,629761603,630397237,631032871,632119577,632755210,633073028,633997080,634921132,636386686,637310738,638090581,639014633,639938685,640718528,642328291,643108134,644032186,644956238,645736081,647345844,648125687,648761321,649396954,649714772,650350406,651437112,652361164,653285216,654065059,654989111,656454665,658064428,658988480,659768323,660692375,661472218,663081981,664006033,664785876,665709928,666489771,681427343,696364915,708616670,723554242,735805997,736730049,738339812,739119655,740043707,740823550,741459184,742094818,743181524,743817157,744134975,745059027,745983079,747448633,748372685,749152528,750076580,751000632,751780475,753390238,754170081,755094133,756018185,756798028,758407791,759187634,759823268,760458901,760776719,761412353,762499059,763423111,764347163,765127006,766051058,767516612,769126375,770050427,770830270,771754322,772534165,774143928,775067980,775847823,776771875,777551718,778475770,780085533,780865376,781789428,782569271,783493323,791424135,792203978,793128030,793907873,794543507,795179141,796265847,796901480,797219298,798143350,799067402,800532956,801457008,802236851,803160903,804084955,804864798,806474561,807254404,808178456,809102508,809882351,811492114,812271957,812907591,813543224,813861042,814496676,815583382,816507434,817431486,818211329,819135381,820600935,821687641,822323275,822958909,823594542,823912360,824999066,825634700,826270334,826905967,827223785,827859419,828946125,829581759,830217392,830535210,831170844,832257550,832893184,833528817,833846635,834482269,835117903,840218689,840854322,841172140,841807774,842443408,843530114,844165747,844483565,845119199,845754833,846390467,847477172,847794990,848430624,849066258,849701892,850788597,851106414,851106414,851106414,851106414,851106414,851106415,851742049,852377683,853013317,853648950,854417840,856027603,856951655,857731498,858655550,859435393,861045156,861969208,862749051,863673103,864452946,865376998,866986761,867766604,868690656,869470499,870394551,872004314,872784157,873708209,874488052,875123686,875759320,876846026,877481659,877799477,878723529,879647581,887434184,888358236,889138079,890062131,890986183,891766026,893375789,894155632,895079684,896003736,896783579,898393342,899173185,899808819,900444452,900762270,901397904,902484610,903408662,904332714,905112557,906036609,907502163,909111926,910035978,910815821,911739873,912519716,914129479,915053531,915833374,916757426,917537269,918461321,920071084,920850927,921774979,922554822,923478874,925088637,925868480,926792532,927572375,928208009,928843643,929930349,930565982,930883800,931807852,932731904,934197458,935121510,935901353,936825405,937749457,938529300,946460112,947239955,948164007,949088059,949867902,951477665,952257508,952893142,953528775,953846593,954482227,955568933,956492985,957417037,958196880,959120932,960586486,962196249,963120301,963900144,964824196,965604039,967213802,968137854,968917697,969841749,970621592,971545644,973155407,973935250,974859302,975639145,976563197,978172960,978952803,979876855,980656698,981292332,981927966,983014672,983650305,983968123,984892175,985816227,987281781,988205833,988985676,989909728,990833780,991613623,993223386,994003229,994927281,995851333,996631176,1004561988,1005341831,1005977465,1006613098,1006930916,1007566550,1008653256,1009577308,1010501360,1011281203,1012205255,1013670809,1014757515,1015393148,1015710966,1016346600,1016982234,1018068940,1018704573,1019022391,1019658025,1020293659,1020929293,1022015998,1022333816,1022969450,1023605084,1024240718,1025327423,1025645241,1026280875,1026916508,1026916508,1026916508,1026916508,1026916508,1026916509,1027552143,1028187776,1028956666,1029592300,1030227934,1030863568,1031499201,1031817019,1032903725,1033539359,1034174993,1034810626,1035128444,1036215150,1036850784,1037486418,1038122051,1038439869,1039075503,1044176289,1044811923,1045447556,1045765374,1046401008,1047487714,1049097477,1050021529,1050801372,1051725424,1052505267,1054115030,1055039082,1055818925,1056742977,1057522820,1058446872,1060056635,1060836478,1061760530,1062540373,1063464425,1065074188,1065854031,1066778083,1067557926,1068193560,1068829194,1069915900,1070551533,1070869351,1071793403,1072717455,1074183009,1075107061,1075886904,1076810956,1077735008,1078514851,1080124614,1080904457,1081828509,1082752561,1083532404,1085142167,1085922010,1086557644,1087193277,1087511095,1088146729,1089233435,1090157487,1091081539,1091861382,1092785434,1100572037,1108502849,1109426901,1110206744,1111130796,1111910639,1113520402,1114444454,1115224297,1116148349,1116928192,1117852244,1119462007,1120241850,1121165902,1121945745,1122869797,1124479560,1125259403,1126183455,1126963298,1127598932,1128234566,1129321272,1129956905,1130274723,1131198775,1132122827,1133588381,1134512433,1135292276,1136216328,1137140380,1137920223,1139529986,1140309829,1141233881,1142157933,1142937776,1144547539,1145327382,1145963016,1146598649,1146916467,1147552101,1148638807,1149562859,1150486911,1151266754,1152190806,1153656360,1155266123,1156190175,1156970018,1157894070,1158673913,1166604725,1167528777,1168308620,1169232672,1170012515,1170936567,1172546330,1173326173,1174250225,1175030068,1175954120,1177563883,1178343726,1179267778,1180047621,1180683255,1181318889,1182405595,1183041228,1183359046,1184283098,1185207150,1186672704,1187596756,1188376599,1189300651,1190224703,1191004546,1192614309,1193394152,1194318204,1195242256,1196022099,1197631862,1198411705,1199047339,1199682972,1200000790,1200636424,1201723130,
1202647182,1203571234,1204351077,1205275129,1206740683,1208350446,1209274498,1210054341,1210978393,1211758236,1213367999,1214292051,1215071894,1215995946,1216775789,1217699841,1225630653,1226410496,1227334548,1228114391,1229038443,1230648206,1231428049,1232352101,1233131944,1233767578,1234403212,1235489918,1236125551,1236443369,1237367421,1238291473,1239757027,1240681079,1241460922,1242384974,1243309026,1244088869,1245698632,1246478475,1247402527,1248326579,1249106422,1250716185,1251496028,1252131662,1252767295,1253085113,1253720747,1254807453,1255731505,1256655557,1257435400,1258359452,1259825006,1261434769,1262358821,1263138664,1264062716,1264842559,1266452322,1267376374,1268156217,1269080269,1269860112,1270784164,1272393927,1273173770,1274097822,1274877665,1289815237,1304752809,1317004564,1331942136,1344193891,1344829525,1345465159,1346551865,1347187498,1347505316,1348429368,1349353420,1350818974,1351743026,1352522869,1353446921,1354370973,1355150816,1356760579,1357540422,1358464474,1359388526,1360168369,1361778132,1362557975,1363193609,1363829242,1364147060,1364782694,1365869400,1366793452,1367717504,1368497347,1369421399,1370886953,1371973659,1372609293,1373244927,1373880560,1374198378,1375285084,1375920718,1376556352,1377191985,1377509803,1378145437,1379232143,1379867777,
1380503410,1380821228,1381456862,1382543568,1383179202,1383814835,1384132653,1384768287,1385403921,1390504707,1391140340,1391458158,1392093792,1392729426,1393816132,1394451765,1394769583,1395405217,1396040851,1396676485,1397763190,1398081008,1398716642,1399352276,1399987910,1401074615,1401392432,1401392432,1401392432,1401392432,1401392432,1401392433,1402028067,1402663701,1403299335,1403934968,1404703858,1406313621,1407237673,1408017516,1408941568,1409721411,1411331174,1412255226,1413035069,1413959121,1414738964,1415663016,1417272779,1418052622,1418976674,1419756517,1420680569,1422290332,1423070175,1423994227,1424774070,1425409704,1426045338,1427132044,1427767677,1428085495,1429009547,1429933599,1437720202,1438644254,1439424097,1440348149,1441272201,1442052044,1443661807,1444441650,1445365702,1446289754,1447069597,1448679360,1449459203,1450094837,1450730470,1451048288,1451683922,1452770628,1453694680,1454618732,1455398575,1456322627,1457788181,1459397944,1460321996,1461101839,1462025891,1462805734,1464415497,1465339549,1466119392,1467043444,1467823287,1468747339,1470357102,1471136945,1472060997,1472840840,1473764892,1475374655,1476154498,1477078550,1477858393,1478494027,1479129661,1480216367,1480852000,1481169818,1482093870,1483017922,1484483476,1485407528,1486187371,1487111423,
1488035475,1488815318,1496746130,1497525973,1498450025,1499374077,1500153920,1501763683,1502543526,1503179160,1503814793,1504132611,1504768245,1505854951,1506779003,1507703055,1508482898,1509406950,1510872504,1512482267,1513406319,1514186162,1515110214,1515890057,1517499820,1518423872,1519203715,1520127767,1520907610,1521831662,1523441425,1524221268,1525145320,1525925163,1526849215,1528458978,1529238821,1530162873,1530942716,1531578350,1532213984,1533300690,1533936323,1534254141,1535178193,1536102245,1537567799,1538491851,1539271694,1540195746,1541119798,1541899641,1543509404,1544289247,1545213299,1546137351,1546917194,1554848006,1555627849,1556263483,1556899116,1557216934,1557852568,1558939274,1559863326,1560787378,1561567221,1562491273,1563956827,1565043533,1565679166,1565996984,1566632618,1567268252,1568354958,1568990591,1569308409,1569944043,1570579677,1571215311,1572302016,1572619834,1573255468,1573891102,1574526736,1575613441,1575931259,1576566893,1577202526,1577202526,1577202526,1577202526,1577202526,1577202527,1577838161,1578473794,1579242684,1579878318,1580513952,1581149586,1581785219,1582103037,1583189743,1583825377,1584461011,1585096644,1585414462,1586501168,1587136802,1587772436,1588408069,1588725887,1589361521,1594462307,1595097941,1595733574,1596051392,1596687026,1597773732,1599383495,1600307547,1601087390,1602011442,1602791285,1604401048,1605325100,1606104943,1607028995,1607808838,1608732890,1610342653,1611122496,1612046548,1612826391,1613750443,1615360206,1616140049,1617064101,1617843944,1618479578,1619115212,1620201918,1620837551,1621155369,1622079421,1623003473,1624469027,1625393079,1626172922,1627096974,1628021026,1628800869,1630410632,1631190475,1632114527,1633038579,1633818422,1635428185,1636208028,1636843662,1637479295,1637797113,1638432747,1639519453,1640443505,1641367557,1642147400,1643071452,1650858055,1655958841,1656594475,1657230109,1657865742,1658183560,1659270266,1659905900,1660541534,1661177167,1661494985,1662130619,1663217325,1663852959,1664488592,1664806410,1665442044,1666528750,1667164384,1667800017,1668117835,1668753469,1669389103,1670475809,1671111442,1671429260,1672064894,1672700528,1673787234,1674422867,1674740685,1675376319,1676011953,1676647587,1677734292,1678052110,1678687744,1679323378,1679959012,1681045717,1681363534,1681363534,1681363534,1681363534,1681363534,1681363535,1681999169,1682634803,1683270437,1683906070,1684674960,1685761666,1686397300,1687032934,1687668567,1687986385,1693087171,1693722805,1694358439,1694994072,1695311890,1695947524,1697034230,1697669864,1698305497,1698623315,1699258949,1700345655,1700981289,1701616922,1701934740,1702570374,1703206008,1704292714,1704928347,1705246165,1705881799,1706517433,1707604139,1708239772,1708557590,1709193224,1709828858,1710464492,1711551197,1711869015,1712504649,1713140283,1713775917,1714862622,1715180439,1715180439,1715180439,1715180439,1715180439,1715180440,1715816074,1716451708,1717087342,1717722975,1718491865,1719578571,1720214205,1720849839,
1721485472,1721803290,1722889996,1723525630,1724161264,1724796897,1725114715,1725750349,1730851135,1731486769,1732122402,1732440220,1733075854,1734162560,1734798194,1735433827,1735751645,1736387279,1737022913,1738109619,1738745252,1739063070,1739698704,1740334338,1741421044,1742056677,1742374495,1743010129,1743645763,1744281397,1745368102,1745685920,1746321554,1746957188,1747592822,1748679527,1748997344,1748997344,1748997344,1748997344,1748997344,1748997345,1749632979,1750268613,1750904247,1751539880,1752308770,1753395476,1754031110,1754666744,1755302377,1755620195,1756706901,1757342535,1757978169,1758613802,1758931620,1759567254,1760653960,1761289594,1761925227,1762243045,1762878679,1767979465,1768615099,1769250732,1769568550,1770204184,1770839818,1771926524,1772562157,1772879975,1773515609,1774151243,1775237949,1775873582,1776191400,1776827034,1777462668,1778098302,1779185007,1779502825,1780138459,1780774093,1781409727,1782496432,1782814249,1782814249,1782814249,1782814249,1782814249,1782814250,1783449884,1784085518,1784721152,1785356785,1786125675,1787212381,1787848015,1788483649,1789119282,1789437100,1790523806,1791159440,1791795074,1792430707,1792748525,1793384159,1794470865,1795106499,1795742132,1796059950,1796695584,1797782290,1798417924,1799053557,1799371375,1808937313,1818503251,1828069189,1837635126,1842418096,1843053730,1843689364,1844776070,1845411703,1845729521,1846365155,1847000789,1847636423,1848723128,1849040946,1849676580,1850312214,1850947848,1852034553,1852352370,1852352370,1852352370,1852352370,1852352370,1852352371,1852988005,1853623639,1854259273,1854894906,1855663796,1856750502,1857386136,1858021770,1858657403,1858975221,1860061927,1860697561,1861333195,1861968828,1862286646,1862922280,1864008986,1864644620,1865280253,1865598071,1866233705,1867320411,1867956045,1868591678,1868909496,1869545130,1870180764,1871267470,1871903103,1872220921,1872856555,1873492189,1878592975,1879228608,1879546426,1880182060,1880817694,1881453328,1882540033,1882857851,1883493485,1884129119,1884764753,1885851458,1886169275,1886169275,1886169275,1886169275,1886169275,1886169276,1886804910,1887440544,1888076178,1888711811,1889480701,1890567407,1891203041,1891838675,1892474308,1892792126,1893878832,1894514466,1895150100,1895785733,1896103551,1896739185,1897825891,1898461525,1899097158,1899414976,1900050610,1901137316,1901772950,1902408583,1902726401,1903362035,1903997669,1905084375,1905720008,1906037826,1906673460,1907309094,1908395800,1909031433,1909349251,1909984885,1910620519,1911256153,1916356938,1916674756,1917310390,1917946024,1918581658,1919668363,1919986180,1919986180,1919986180,1919986180,1919986180,1919986181,1920621815,1921257449,1921893083,1922528716,1923297606,1924384312,1925019946,1925655580,1926291213,1926609031,1927695737,1928331371,1928967005,1929602638,1929920456,1930556090,1931642796,1932278430,1932914063,1933231881,1933867515,1934954221,1935589855,1936225488,1936543306,1937178940,1937814574,1938901280,1939536913,1939854731,1940490365,1941125999,1942212705,1942848338,1943166156,1943801790,1944437424,1945073058,1946159763,1946477581,1947113215,1947748849,1948384483,1953485268,1953803085,
1953803085,1953803085,1953803085,1953803085,1953803086,1954438720,1955074354,1955709988,1956345621,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114510,1957114511,1958201217,1958836851,1959472485,1960108118,1960425936,1961512642,1962148276,1962783910,1963419543,1963737361,1964372995,1965459701,1966095335,1966730968,1967048786,1967684420,1968771126,1969406760,1970042393,1970360211,1970995845,1971631479,1972718185,1973353818,1973671636,1974307270,1974942904,1976029610,1976665243,1976983061,1977618695,1978254329,1978889963,1979976668,1980294486,1980930120,1981565754,1982201388,1983288093,1983605910,1983605910,1983605910,1983605910,1983605910,1983605911,1984241545,1984877179,1985512813,1986148446,1990931416,1998862228,1999786280,2000566123,2001490175,2002270018,2003879781,2004803833,2005583676,2006507728,2007287571,2008211623,2009821386,2010601229,2011525281,2012305124,2013229176,2014838939,2015618782,2016542834,2017322677,2017958311,2018593945,2019680651,2020316284,2020634102,2021558154,2022482206,2023947760,2024871812,2025651655,2026575707,2027499759,2028279602,2029889365,2030669208,2031593260,2032517312,2033297155,2034906918,2035686761,2036322395,2036958028,2037275846,2037911480,2038998186,2039922238,2040846290,2041626133,2042550185,2044015739,2045625502,2046549554,2047329397,2048253449,2049033292,2056964104,2057888156,2058667999,2059592051,2060371894,2061295946,2062905709,2063685552,2064609604,2065389447,2066313499,2067923262,2068703105,2069627157,2070407000,2071042634,2071678268,2072764974,2073400607,2073718425,2074642477,2075566529,2077032083,2077956135,2078735978,2079660030,2080584082,2081363925,2082973688,2083753531,2084677583,2085601635,2086381478,2087991241,2088771084,2089406718,2090042351,2090360169,2090995803,2092082509,2093006561,2093930613,2094710456,2095634508,2097100062,2098709825,2099633877,2100413720,2101337772,2102117615,2103727378,2104651430,2105431273,2106355325,2107135168,2108059220,2115990032,2116769875,2117693927,2118473770,2119397822,2121007585,2121787428,2122711480,2123491323,2124126957,2124762591,2125849297,2126484930,2126802748,2127726800,2128650852,2130116406,2131040458,2131820301,2132744353,2133668405,2134448248,2136058011,2136837854,2137761906,2138685958,2139465801,2141075564,2141855407,2142491041,2143126674,2143444492,2144080126,2145166832,2146090884,2147014936,2147794779,2148718831,2150184385,2151794148,2152718200,2153498043,2154422095,2155201938,2156811701,2157735753,2158515596,2159439648,2160219491,2161143543,2162753306,2163533149,2164457201,2165237044,2166161096,2174091908,2174871751,2175795803,2176575646,2177211280,2177846914,2178933620,2179569253,2179887071,2180811123,2181735175,2183200729,2184124781,2184904624,2185828676,2186752728,2187532571,2189142334,2189922177,2190846229,2191770281,2192550124,2194159887,2194939730,2195575364,2196210997,2196528815,2197164449,2198251155,2199175207,2200099259,2200879102,2201803154,2203268708,2204355414,2204991048,2205626682,2206262315,2206580133,2207666839,2208302473,2208938107,2209573740,2209891558,2210527192,2211613898,2212249532,2212885165,2213202983,2213838617,2214925323,2215560957,2216196590,2216514408,2217150042,2217785676,2222886462,
2223522095,2223839913,2224475547,2225111181,2226197887,2226833520,2227151338,2227786972,2228422606,2229058240,2230144945,2230462763,2231098397,2231734031,2232369665,2233456370,2233774187,2233774187,2233774187,2233774187,2233774187,2233774188,2234409822,2235045456,2235681090,2236316723,2237085613,2238695376,2239619428,2240399271,2241323323,2242103166,2243712929,2244636981,2245416824,2246340876,2247120719,2248044771,2249654534,2250434377,2251358429,2252138272,2253062324,2254672087,2255451930,2256375982,2257155825,2257791459,2258427093,2259513799,2260149432,2260467250,2275404822,2290342394,2302594149,2317531721,2329783476,2330707528,2331631580,2332411423,2334021186,2334801029,2335725081,2336649133,2337428976,2339038739,2339818582,2340454216,2341089849,2341407667,2342043301,2343130007,2344054059,2344978111,2345757954,2346682006,2348147560,2349757323,2350681375,2351461218,2352385270,2353165113,2354774876,2355698928,2356478771,2357402823,2358182666,2359106718,2360716481,2361496324,2362420376,2363200219,2364124271,2365734034,2366513877,2367437929,2368217772,2368853406,2369489040,2370575746,2371211379,2371529197,2372453249,2373377301,2374842855,2375766907,2376546750,2377470802,2378394854,2379174697,2387105509,2387885352,2388809404,2389733456,2390513299,2392123062,2392902905,2393538539,2394174172,2394491990,2395127624,2396214330,2397138382,2398062434,2398842277,2399766329,2401231883,2402841646,2403765698,2404545541,2405469593,2406249436,2407859199,2408783251,2409563094,2410487146,2411266989,2412191041,2413800804,2414580647,2415504699,2416284542,2417208594,2418818357,2419598200,2420522252,2421302095,2421937729,2422573363,2423660069,2424295702,2424613520,2425537572,2426461624,2427927178,2428851230,2429631073,2430555125,2431479177,2432259020,2433868783,2434648626,2435572678,2436496730,2437276573,2445207385,2445987228,2446622862,2447258495,2447576313,2448211947,2449298653,2450222705,2451146757,2451926600,2452850652,2454316206,2455402912,2456038545,2456356363,2456991997,2457627631,2458714337,2459349970,2459667788,2460303422,2460939056,2461574690,2462661395,2462979213,2463614847,2464250481,2464886115,2465972820,2466290638,2466926272,2467561905,2467561905,2467561905,2467561905,2467561905,2467561906,2468197540,2468833173,2469602063,2470237697,2470873331,2471508965,2472144598,2472462416,2473549122,2474184756,2474820390,2475456023,2475773841,2476860547,2477496181,2478131815,2478767448,2479085266,2479720900,2484821686,2485457320,2486092953,2486410771,2487046405,2488133111,2489742874,2490666926,2491446769,2492370821,2493150664,2494760427,2495684479,2496464322,2497388374,2498168217,2499092269,2500702032,2501481875,2502405927,2503185770,2504109822,2505719585,2506499428,2507423480,2508203323,2508838957,2509474591,2510561297,2511196930,2511514748,2512438800,2513362852,2514828406,2515752458,2516532301,2517456353,2518380405,2519160248,2520770011,2521549854,2522473906,2523397958,2524177801,2525787564,2526567407,2527203041,2527838674,2528156492,2528792126,2529878832,2530802884,2531726936,2532506779,2533430831,2541217434,2549148246,2550072298,2550852141,2551776193,2552556036,2554165799,2555089851,2555869694,2556793746,2557573589,2558497641,2560107404,2560887247,2561811299,2562591142,2563515194,2565124957,2565904800,2566828852,2567608695,2568244329,2568879963,2569966669,2570602302,2570920120,2571844172,2572768224,2574233778,2575157830,2575937673,2576861725,2577785777,2578565620,2580175383,2580955226,2581879278,2582803330,2583583173,2585192936,2585972779,2586608413,2587244046,2587561864,2588197498,2589284204,2590208256,2591132308,2591912151,2592836203,2594301757,2595911520,2596835572,2597615415,2598539467,2599319310,2607250122,2608174174,2608954017,2609878069,2610657912,2611581964,2613191727,2613971570,2614895622,2615675465,2616599517,2618209280,2618989123,2619913175,2620693018,2621328652,2621964286,2623050992,2623686625,2624004443,2624928495,2625852547,2627318101,2628242153,2629021996,2629946048,2630870100,2631649943,2633259706,2634039549,2634963601,2635887653,2636667496,2638277259,2639057102,2639692736,2640328369,2640646187,2641281821,2642368527,2643292579,2644216631,2644996474,2645920526,2647386080,2648995843,2649919895,2650699738,2651623790,2652403633,2654013396,2654937448,2655717291,2656641343,2657421186,2658345238,2666276050,2667055893,2667979945,2668759788,
2669683840,2671293603,2672073446,2672997498,2673777341,2674412975,2675048609,2676135315,2676770948,2677088766,2678012818,2678936870,2680402424,2681326476,2682106319,2683030371,2683954423,2684734266,2686344029,2687123872,2688047924,2688971976,2689751819,2691361582,2692141425,2692777059,2693412692,2693730510,2694366144,2695452850,2696376902,2697300954,2698080797,2699004849,2700470403,2702080166,2703004218,2703784061,2704708113,2705487956,2707097719,2708021771,2708801614,2709725666,2710505509,2711429561,2713039324,2713819167,2714743219,2715523062,2716447114,2724377926,2725157769,2726081821,2726861664,2727497298,2728132932,2729219638,2729855271,2730173089,2731097141,2732021193,2733486747,2734410799,2735190642,2736114694,2737038746,2737818589,2739428352,2740208195,2741132247,2742056299,2742836142,2744445905,2745225748,2745861382,2746497015,2746814833,2747450467,2748537173,2749461225,2750385277,2751165120,2752089172,2753554726,2754641432,2755277066,2755912700,2756548333,2756866151,2757952857,2758588491,2759224125,2759859758,2760177576,2760813210,2761899916,2762535550,2763171183,2763489001,2764124635,2765211341,2765846975,2766482608,2766800426,2767436060,2768071694,2773172480,2773808113,2774125931,2774761565,2775397199,2776483905,2777119538,2777437356,2778072990,2778708624,2779344258,2780430963,2780748781,2781384415,2782020049,2782655683,2783742388,2784060205,2784060205,2784060205,2784060205,2784060205,2784060206,2784695840,2785331474,2785967108,2786602741,2787371631,2788981394,2789905446,2790685289,2791609341,2792389184,2793998947,2794922999,2795702842,2796626894,2797406737,2798330789,2799940552,2800720395,2801644447,2802424290,2803348342,2804958105,2805737948,2806662000,2807441843,2808077477,2808713111,2809799817,2810435450,2810753268,2811677320,2812601372,2820387975,2821312027,2822091870,2823015922,2823939974,2824719817,2826329580,2827109423,2828033475,2828957527,2829737370,2831347133,2832126976,2832762610,2833398243,2833716061,2834351695,2835438401,2836362453,2837286505,2838066348,2838990400,2840455954,2842065717,2842989769,2843769612,2844693664,2845473507,2847083270,2848007322,2848787165,
2849711217,2850491060,2851415112,2853024875,2853804718,2854728770,2855508613,2856432665,2858042428,2858822271,2859746323,2860526166,2861161800,2861797434,2862884140,2863519773,2863837591,2864761643,2865685695,2867151249,2868075301,2868855144,2883792716,2898730288,2910982043,2925919615,2938171370,2939095422,2940019474,2940799317,2942409080,2943188923,2943824557,2944460190,2944778008,2945413642,2946500348,2947424400,2948348452,2949128295,2950052347,2951517901,2953127664,2954051716,2954831559,2955755611,2956535454,2958145217,2959069269,2959849112,2960773164,2961553007,2962477059,2964086822,2964866665,2965790717,2966570560,2967494612,2969104375,2969884218,2970808270,2971588113,2972223747,2972859381,2973946087,2974581720,2974899538,2975823590,2976747642,2978213196,2979137248,2979917091,2980841143,2981765195,2982545038,2984154801,2984934644,2985858696,2986782748,2987562591,2995493403,2996273246,2996908880,2997544513,2997862331,2998497965,2999584671,3000508723,3001432775,3002212618,3003136670,3004602224,3005688930,3006324563,3006642381,3007278015,3007913649,3009000355,3009635988,3009953806,3010589440,3011225074,3011860708,3012947413,3013265231,3013900865,3014536499,3015172133,3016258838,3016576656,3017212290,3017847923,3017847923,3017847923,3017847923,3017847923,3017847924,3018483558,3019119191,3019888081,3020523715,3021159349,3021794983,3022430616,3022748434,3023835140,3024470774,3025106408,3025742041,3026059859,3027146565,3027782199,3028417833,3029053466,3029371284,3030006918,3035107704,3035743338,3036378971,3036696789,3037332423,3038419129,3040028892,3040952944,3041732787,3042656839,3043436682,3045046445,3045970497,3046750340,3047674392,3048454235,3049378287,3050988050,3051767893,3052691945,3053471788,3054395840,3056005603,3056785446,3057709498,3058489341,3059124975,3059760609,3060847315,3061482948,3061800766,3062724818,3063648870,3065114424,3066038476,3066818319,3067742371,3068666423,3069446266,3071056029,3071835872,3072759924,3073683976,3074463819,3076073582,3076853425,3077489059,3078124692,3078442510,3079078144,3080164850,3081088902,3082012954,3082792797,3083716849,3091503452,3099434264,3100358316,3101138159,3102062211,3102842054,3104451817,3105375869,3106155712,3107079764,3107859607,3108783659,3110393422,3111173265,3112097317,3112877160,3113801212,3115410975,3116190818,3117114870,3117894713,3118530347,3119165981,3120252687,3120888320,3121206138,3122130190,3123054242,3124519796,3125443848,3126223691,3127147743,3128071795,3128851638,3130461401,3131241244,3132165296,3133089348,3133869191,3135478954,3136258797,3136894431,3137530064,3137847882,3138483516,3139570222,3140494274,3141418326,3142198169,3143122221,3144587775,3146197538,3147121590,3147901433,3148825485,3149605328,3157536140,3158460192,3159240035,3160164087,3160943930,3161867982,3163477745,3164257588,3165181640,3165961483,3166885535,3168495298,3169275141,3170199193,3170979036,3171614670,3172250304,3173337010,3173972643,3174290461,3175214513,3176138565,3177604119,3178528171,3179308014,3180232066,3181156118,3181935961,3183545724,3184325567,3185249619,3186173671,3186953514,3188563277,3189343120,3189978754,3190614387,3190932205,3191567839,3192654545,3193578597,3194502649,3195282492,3196206544,3197672098,3199281861,3200205913,3200985756,3201909808,3202689651,3204299414,3205223466,3206003309,3206927361,3207707204,3208631256,3216562068,3217341911,3218265963,3219045806,3219969858,3221579621,3222359464,3223283516,3224063359,3224698993,3225334627,3226421333,3227056966,3227374784,3228298836,3229222888,3230688442,3231612494,3232392337,3233316389,3234240441,3235020284,3236630047,3237409890,3238333942,3239257994,3240037837,3241647600,3242427443,3243063077,3243698710,3244016528,3244652162,3245738868,3246662920,3247586972,3248366815,3249290867,3250756421,3252366184,3253290236,3254070079,3254994131,3255773974,3257383737,3258307789,3259087632,3260011684,3260791527,3261715579,3263325342,3264105185,3265029237,3265809080,3266733132,3274663944,3275443787,3276367839,3277147682,3277783316,3278418950,3279505656,3280141289,3280459107,3281383159,3282307211,3283772765,3284696817,3285476660,3286400712,3287324764,3288104607,3289714370,3290494213,3291418265,3292342317,3293122160,3294731923,3295511766,3296147400,3296783033,3297100851,3297736485,3298823191,3299747243,3300671295,3301451138,3302375190,3303840744,3304927450,3305563084,3306198718,3306834351,3307152169,3308238875,3308874509,3309510143,3310145776,3310463594,3311099228,3312185934,3312821568,3313457201,3313775019,3314410653,3315497359,3316132993,3316768626,3317086444,3317722078,3318357712,3323458498,3324094131,3324411949,3325047583,3325683217,3326769923,3327405556,3327723374,3328359008,3328994642,3329630276,3330716981,3331034799,3331670433,3332306067,3332941701,3334028406,3334346223,3334346223,3334346223,3334346223,3334346223,3334346224,3334981858,3335617492,3336253126,3336888759,3337657649,3339267412,3340191464,3340971307,3341895359,3342675202,3344284965,3345209017,3345988860,3346912912,3347692755,3348616807,3350226570,3351006413,3351930465,3352710308,3353634360,3355244123,3356023966,3356948018,3357727861,3358363495,3358999129,3360085835,3360721468,3361039286,3361963338,3362887390,3370673993,3371598045,3372377888,3373301940,3374225992,3375005835,3376615598,3377395441,3378319493,3379243545,3380023388,3381633151,3382412994,3383048628,3383684261,3384002079,3384637713,3385724419,3386648471,3387572523,3388352366,3389276418,3390741972,3392351735,3393275787,3394055630,3394979682,3395759525,3397369288,3398293340,3399073183,3399997235,3400777078,3401701130,3403310893,3404090736,3405014788,3405794631,3406718683,3408328446,3409108289,3410032341,3410812184,3411447818,3412083452,3413170158,3413805791,3414123609,3415047661,3415971713,3417437267,3418361319,3419141162,3420065214,3420989266,3421769109,3429699921,3430479764,3431403816,3432327868,3433107711,3434717474,3435497317,3436132951,3436768584,3437086402,3437722036,3438808742,3439732794,3440656846,3441436689,3442360741,3443826295,3445436058,
3446360110,3447139953,3448064005,3448843848,3450453611,3451377663,3452157506,3453081558,3453861401,3454785453,3456395216,3457175059,3458099111,3458878954,3459803006,3461412769,3462192612,3463116664,3463896507,3464532141,3465167775,3466254481,3466890114,3467207932,3468131984,3469056036,3470521590,3471445642,3472225485,3473149537,3474073589,3474853432,3476463195,3477243038,3492180610,3507118182,3519369937,3534307509,3546559264,3547194898,3547830531,3548148349,3548783983,3549870689,3550794741,3551718793,3552498636,3553422688,3554888242,3555974948,3556610581,3556928399,3557564033,3558199667,3559286373,3559922006,3560239824,3560875458,3561511092,3562146726,3563233431,3563551249,3564186883,3564822517,3565458151,3566544856,3566862674,3567498308,3568133941,3568133941,3568133941,3568133941,3568133941,3568133942,3568769576,3569405209,3570174099,3570809733,3571445367,3572081001,3572716634,3573034452,3574121158,3574756792,3575392426,3576028059,3576345877,3577432583,3578068217,3578703851,3579339484,3579657302,3580292936,3585393722,3586029356,3586664989,3586982807,3587618441,3588705147,3590314910,3591238962,3592018805,3592942857,3593722700,3595332463,3596256515,3597036358,3597960410,3598740253,3599664305,3601274068,3602053911,3602977963,3603757806,3604681858,3606291621,3607071464,3607995516,3608775359,3609410993,3610046627,3611133333,3611768966,3612086784,3613010836,3613934888,3615400442,3616324494,3617104337,3618028389,3618952441,3619732284,3621342047,3622121890,3623045942,3623969994,3624749837,3626359600,3627139443,3627775077,3628410710,3628728528,3629364162,3630450868,3631374920,3632298972,3633078815,3634002867,3641789470,3646890256,3647525889,3647843707,3648479341,3649114975,3650201681,3650837314,3651155132,3651790766,3652426400,3653062034,3654148739,3654466557,3655102191,3655737825,3656373459,3657460164,3657777982,3658413616,3659049249,3659049249,3659049249,3659049249,3659049249,3659049250,3659684884,3660320517,3661089407,3661725041,3662360675,3662996309,3663631942,3663949760,3665036466,3665672100,3666307734,3666943367,3667261185,3668347891,3668983525,3669619159,3670254792,3670572610,3671208244,3672294950,3672930584,3673566217,3673884035,3674519669,3675606375,3676693081,3677328714,3677646532,3678282166,3678917800,3684018586,3684654219,3684972037,3685607671,3686243305,3686878939,3687965644,3688283462,3688919096,3689554730,3690190364,3691277069,3691594887,3692230521,3692866154,3692866154,3692866154,3692866154,3692866154,3692866155,3693501789,3694137422,3694906312,3695541946,3696177580,3696813214,3697448847,3697766665,3698853371,3699489005,3700124639,3700760272,3701078090,3702164796,3702800430,3703436064,3704071697,3704389515,3705025149,3706111855,3706747489,3707383122,3707700940,3708336574,3709423280,3710509986,3711145619,3711463437,3712099071,3712734705,3713821411,3714457044,3714774862,3715410496,3716046130,3716681764,3721782549,3722100367,3722736001,3723371635,3724007269,3725093974,3725411792,3726047426,3726683059,3726683059,3726683059,3726683059,3726683059,3726683060,3727318694,
3727954327,3728723217,3729358851,3729994485,3730630119,3731265752,3731583570,3732670276,3733305910,3733941544,3734577177,3734894995,3735981701,3736617335,3737252969,3737888602,3738206420,3738842054,3739928760,3740564394,3741200027,3741517845,3742153479,3743240185,3744326891,3744962524,3745280342,3745915976,3746551610,3747638316,3748273949,3748591767,3749227401,3749863035,
3750498669,3751585374,3751903192,3752538826,3753174460,3753810094,3758910879,3759228697,3759864331,3760499964,3760499964,3760499964,3760499964,3760499964,3760499965,3761135599,3761771232,3762540122,3763175756,3763811390,3764447024,3765082657,3765400475,3766487181,3767122815,3767758449,3768394082,3768711900,3769798606,3770434240,3771069874,3771705507,3772023325,3772658959,3773745665,3774381299,3775016932,3775334750,3775970384,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057089,3777057090,3778143796,3778779429,3779097247,3779732881,3780368515,3781455221,3782090854,3782408672,3783044306,3783679940,3784315574,3785402279,3785720097,3786355731,3786991365,3787626999,3788713704,3789031522,3789667156,3790302789,3790302789,3790302789,3790302789,3790302789,3790302790,3790938424,3791574057,3796357027,3796992661,3797628295,3798263929,3798899562,3799217380,3800304086,3800939720,3801575354,3802210987,3802528805,3803615511,3804251145,3804886779,3805522412,3805840230,3806475864,3807562570,3808198204,3808833837,3809151655,3809787289,3810873995,3811960701,3812596334,3812914152,3813549786,3814185420,3815272126,3815907759,3816225577,3816861211,3817496845,3818132479,
3819219184,3819537002,3820172636,3820808270,3821443904,3822530609,3822848427,3823484061,3824119694,3824119694,3824119694,3824119694,3824119694,3824119695,3824755329,3825390962,3826159852,3826795486,3827431120,3828066754,3828702387,3829020205,3834120991,3834756625,3835392259,3836027892,3836345710,3837432416,3838068050,3838703684,3839339317,3839657135,3840292769,3841379475,3842015109,3842650742,3842968560,3843604194,3844690900,3845777606,3846413239,3846731057,3847366691,3848002325,3849089031,3849724664,3850042482,3850678116,3851313750,3851949384,3853036089,3853353907,3853989541,3854625175,3855260809,3856347514,3856665332,3857300966,3857936599,3857936599,3857936599,3857936599,3857936599,3857936600,3858572234,3859207867,3859976757,3860612391,3861248025,3861883659,3862519292,3862837110,3863923816,3864559450,3865195084,3865830717,3866148535,3871249321,3871884955,3872520589,3873156222,3873474040,3874109674,3875196380,3875832014,3876467647,3876785465,3877421099,3878507805,3879594511,3880230144,3880547962,3881183596,3881819230,3882905936,3883541569,3883859387,3884495021,3885130655,3885766289,3886852994,3887170812,3887806446,3888442080,3889077714,3890164419,3890482237,3891117871,3891753504,3891753504,3891753504,3891753504,3891753504,3891753505,3892389139,3893024772,3893793662,3894429296,3895064930,3895700564,3896336197,3896654015,3897740721,3898376355,3899011989,3899647622,3899965440,3901052146,3901687780,3911253718,3920819655,3925602625,3935168563,3944734501,3945370135,3946005768,3946323586,3946959220,3948045926,3949132632,3949768265,3950086083,3950721717,3951357351,3952444057,3953079690,3953397508,3954033142,3954668776,3955304410,3956391115,3956708933,3957344567,3957980201,3958615835,3959702540,3960020358,3960655992,3961291625,3961291625,3961291625,3961291625,3961291625,3961291626,3961927260,3962562893,3963331783,3963967417,3964603051,3965238685,3965874318,3966192136,3967278842,3967914476,3968550110,3969185743,3969503561,3970590267,3971225901,3971861535,3972497168,3972814986,3973450620,3974537326,3975172960,3975808593,3976126411,3976762045,3981862831,3989793643,3990717695,3991497538,3992421590,3993201433,3994811196,3995735248,3996515091,3997439143,3998218986,3999143038,4000752801,4001532644,4002456696,4003236539,4004160591,4005770354,4006550197,4007474249,4008254092,4008889726,4009525360,4010612066,4011247699,4011565517,4012489569,4013413621,4014879175,4015803227,4016583070,4017507122,4018431174,4019211017,4020820780,4021600623,4022524675,4023448727,4024228570,4025838333,4026618176,4027253810,4027889443,4028207261,4028842895,4029929601,4030853653,4031777705,4032557548,4033481600,4034947154,4036556917,4037480969,4038260812,4039184864,4039964707,4047895519,4048819571,4049599414,4050523466,4051303309,4052227361,4053837124,4054616967,4055541019,4056320862,4057244914,4058854677,4059634520,4060558572,4061338415,4061974049,4062609683,4063696389,4064332022,4064649840,4065573892,4066497944,4067963498,4068887550,4069667393,4070591445,4071515497,4072295340,4073905103,4074684946,4075608998,4076533050,4077312893,4078922656,4079702499,4080338133,4080973766,4081291584,4081927218,4083013924,4083937976,4084862028,4085641871,4086565923,4088031477,4089641240,4090565292,4091345135,4092269187,4093049030,4094658793,4095582845,4096362688,4097286740,4098066583,4098990635,4106921447,4107701290,4108625342,4109405185,4110329237,4111939000,4112718843,4113642895,4114422738,4115058372,4115694006,4116780712,4117416345,4117734163,4118658215,4119582267,4121047821,4121971873,
4122751716,4123675768,4124599820,4125379663,4126989426,4127769269,4128693321,4129617373,4130397216,4132006979,4132786822,4133422456,4134058089,4134375907,4135011541,4136098247,4137022299,4137946351,4138726194,4139650246,4141115800,4142725563,4143649615,4144429458,4145353510,4146133353,4147743116,4148667168,4149447011,4150371063,4151150906,4152074958,4153684721,4154464564,4155388616,4156168459,4157092511,4165023323,4165803166,4166727218,4167507061,4168142695,4168778329,4169865035,4170500668,4170818486,4171742538,4172666590,4174132144,4175056196,4175836039,4176760091,4177684143,4178463986,4180073749,4180853592,4181777644,4182701696,4183481539,4185091302,4185871145,4186506779,4187142412,4187460230,4188095864,4189182570,4190106622,4191030674,4191810517,4192734569,4194200123,4195286829,4195922463,4196558097,4197193730,4197511548,4198598254,4199233888,4199869522,4200505155,4200822973,4201458607,4202545313,4203180947,4203816580,4204134398,4204770032,4205856738,4206492372,4207128005,4207445823,4208081457,4208717091,4213817877,4214453510,4214771328,4215406962,4216042596,4217129302,4217764935,4218082753,4218718387,4219354021,4219989655,4221076360,4221394178,4222029812,4222665446,4223301080,4224387785,4224705602,4224705602,4224705602,4224705602,4224705602,4224705603,4225341237,4225976871,4226612505,4227248138,4228017028,4229626791,4230550843,4231330686,4232254738,4233034581,4234644344,4235568396,4236348239,4237272291,4238052134,4238976186,4240585949,4241365792,4242289844,4243069687,4243993739,4245603502,4246383345,4247307397,4248087240,4248722874,4249358508,4250445214,4251080847,4251398665,4252322717,4253246769,4261033372,4261957424,4262737267,4263661319,4264585371,4265365214,4266974977,4267754820,4268678872,4269602924,4270382767,4271992530,4272772373,4273408007,4274043640,4274361458,4274997092,4276083798,4277007850,4277931902,4278711745,4279635797,4281101351,4282711114,4283635166,4284415009,4285339061,4286118904,4287728667,4288652719,4289432562,4290356614,4291136457,4292060509,4293670272,4294450115,4295374167,4296154010,4297078062,4298687825,4299467668,4300391720,4301171563,4301807197,4302442831,4303529537,4304165170,4304482988,4305407040,4306331092,4307796646,4308720698,4309500541,4310424593,4311348645,4312128488,4320059300,4320839143,4321763195,4322687247,4323467090,4325076853,4325856696,4326492330,4327127963,4327445781,4328081415,4329168121,4330092173,4331016225,4331796068,4332720120,4334185674,4335795437,4336719489,4337499332,4338423384,4339203227,4340812990,4341737042,4342516885,4343440937,4344220780,4345144832,4346754595,4347534438,4348458490,4349238333,4350162385,4351772148,4352551991,4353476043,4354255886,4354891520,4355527154,4356613860,4357249493,4357567311,4358491363,4359415415,4360880969,4361805021,4362584864,4363508916,4364432968,4365212811,4366822574,4367602417,4368526469,4369450521,4370230364,4378161176,4378941019,4379576653,4380212286,4380530104,4381165738,4382252444,4383176496,4384100548,4384880391,4385804443,4387269997,4388356703,4388992336,4389310154,4389945788,4390581422,4391668128,4392303761,4392621579,4393257213,4393892847,4394528481,4395615186,4395933004,4396568638,4397204272,4397839906,4398926611,4399244429,4399880063,4400515696,4400515696,4400515696,4400515696,4400515696,4400515697,4401151331,4401786964,4402555854,4403191488,4403827122,4404462756,4405098389,4405416207,4406502913,4407138547,4407774181,4408409814,4408727632,4409814338,4410449972,4411085606,4411721239,4412039057,4412674691,4417775477,4418411111,4419046744,4419364562,4420000196,4421086902,4422696665,4423620717,4424400560,4425324612,4426104455,4427714218,4428638270,4429418113,4430342165,4431122008,4432046060,4433655823,4434435666,4435359718,4436139561,4437063613,4438673376,4439453219,4440377271,4441157114,4441792748,4442428382,4443515088,4444150721,4444468539,4445392591,4446316643,4447782197,4448706249,4449486092,4450410144,4451334196,4452114039,4453723802,4454503645,4455427697,4456351749,4457131592,4458741355,4459521198,4460156832,4460792465,4461110283,4461745917,4462832623,4477770195,4492707767,4504959522,4519897094};
inline bool check(int x){
    char pre1,pre2;
    pre2=x%10,x/=10;
    pre1=x%10,x/=10;
    bool flag=0,f1=0,f2=0;
    if(pre1==4 || pre2==4) f1=1;
    if(pre1==8 || pre2==8) f2=1;
    while(x){
        char u=x%10;
        if(u==pre1 && pre1==pre2) flag=1;
        if(u==4) f1=1;if(u==8) f2=1;
        if(f1 && f2) return 0;
        pre2=pre1,pre1=u,x/=10;
    }
    return (f1 && f2) ? 0 : flag;
}
int ask(int x){
    if(x<n) return 1;
    signed u=(x-n)/t;
    int q=x/t*t;
    int ans=a[u];
    for(int i=q;i<=x;i++) ans+=check(i);
    return ans;
}
signed main() {
    int l,r;
    cin>>l>>r;
    cout<<ask(r)-ask(l-1);//前缀和
    return 0;
}

:::: 需要整整跑 40 分钟的打表。

习题。

[SCOI2009] windy 数。

这题的 n 都在 10^9 数量级。

所以用 l=2\times 10^7 不会浪费太多时间。

注意事项

在考场上遇到这种题，可以分段打表。

但是有三个注意事项。

一，注意码长。

二，注意空间。

三，注意常数