hdu 4398多校連合試合第9試合X mod f(x)数論
47087 ワード
X mod f(x)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 174 Accepted Submission(s): 42
Problem Description
Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10
9), how many integer x that mod f(x) equal to 0.
Input
The first line has an integer T (1 <= T <= 50), indicate the number of test cases.
Each test case has two integers A, B.
Output
For each test case, output only one line containing the case number and an integer indicated the number of x.
SampleInput
SampleOutput
Author
WHU
タイトル:
入力n m nからmまでx%f(x)を満たす数の個数を算出する
考え方:
最初は法則を探して規則がない.
その後、一部の暴力を考えたのは、時計を書くことです.
1から
1*200000
2*200000
3*200000
.....
10^9
の意味を満たす個数はすべて表に打って出てきてファイルに打ち込んで更に配列の中にコピーします
次に、例えば、1つの入力に対するn=620000
では、1~6000万の数がすでに表に出ているので、暴力60000+1から620000であればいいことがわかります.
acコード 以下に打表コードがあります
打表コード:
注意長さ1000のテーブルタイムアウト 長さ10000のテーブル制限コード長はコミットされません 5000でちょうどいいです
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 174 Accepted Submission(s): 42
Problem Description
Here is a function f(x):
int f ( int x ) {
if ( x == 0 ) return 0;
return f ( x / 10 ) + x % 10;
}
Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10
9), how many integer x that mod f(x) equal to 0.
Input
The first line has an integer T (1 <= T <= 50), indicate the number of test cases.
Each test case has two integers A, B.
Output
For each test case, output only one line containing the case number and an integer indicated the number of x.
SampleInput
2
1 10
11 20
SampleOutput
Case 1: 10
Case 2: 3
Author
WHU
タイトル:
入力n m nからmまでx%f(x)を満たす数の個数を算出する
考え方:
最初は法則を探して規則がない.
その後、一部の暴力を考えたのは、時計を書くことです.
1から
1*200000
2*200000
3*200000
.....
10^9
の意味を満たす個数はすべて表に打って出てきてファイルに打ち込んで更に配列の中にコピーします
次に、例えば、1つの入力に対するn=620000
では、1~6000万の数がすでに表に出ているので、暴力60000+1から620000であればいいことがわかります.
acコード 以下に打表コードがあります
#include
#include
int a[5050]=
{
0,23038,43691,62344,79494,95428,117251,136926,154753,171215,186561,
207319,226142,243273,259122,273964,293749,311777,328266,343560,357923,
376842,394196,410102,424906,438795,456935,473705,489121,503491,516988,
534432,550627,565578,579518,592666,609471,625153,639668,653243,666027,
682185,697359,711460,724669,737096,752684,767362,781082,793957,806095,
827912,847505,865348,881829,897228,917958,936644,953748,969593,984457,
1004246,1022150,1038599,1053893,1068251,1087182,1104383,1120224,1134999,1148898,
1167083,1183663,1198988,1213284,1226769,1244283,1260310,1275181,1289050,1302141,
1319012,1334553,1348965,1362477,1375194,1391506,1406579,1420620,1433752,1446173,
1461907,1476483,1490129,1502903,1514990,1530199,1544339,1557612,1570094,1581855,
1602519,1621202,1638352,1654240,1669171,1688855,1706723,1723174,1738471,1752886,
1771743,1788901,1804751,1819529,1833499,1851587,1868075,1883358,1897646,1911166,
1928604,1944532,1959309,1973139,1986220,2003059,2018498,2032861,2046299,2059035,
2075318,2090283,2104235,2117319,2129704,2145464,2159997,2173585,2186330,2198383,
2213611,2227715,2240925,2253328,2265047,2279834,2293525,2306406,2318480,2329984,
2349563,2367444,2383947,2399319,2413838,2432533,2449651,2465529,2480347,2494379,
2512304,2528778,2544072,2558405,2571992,2589245,2605125,2619881,2633724,2646896,
2663574,2678924,2693224,2706624,2719392,2735522,2750405,2764291,2777339,2789743,
2805369,2819833,2833334,2846056,2858080,2873233,2887292,2900473,2912873,2924630,
2939314,2952939,2965768,2977813,2989257,3003491,3016763,3029225,3040992,3052160,
3070810,3087935,3103866,3118775,3132961,3150784,3167212,3182541,3196945,3210653,
3227800,3243650,3258456,3272346,3285645,3302173,3317444,3331742,3345157,3358037,
3374014,3388829,3402658,3415677,3428135,3443601,3457971,3471414,3484045,3496170,
3511200,3525126,3538227,3550533,3562323,3576928,3590511,3603263,3615293,3626798,
3640941,3654135,3666545,3678248,3689474,3703248,3716068,3728163,3739560,3750525,
3768368,3784857,3800280,3814795,3828640,3845731,3861558,3876416,3890413,3903809,
3920254,3935541,3949897,3963419,3976405,3992271,4007043,4020913,4033968,4046550,
4061913,4076225,4089680,4102288,4114501,4129399,4143282,4156326,4168604,4180462,
4194923,4208446,4221125,4233077,4244641,4258729,4271874,4284236,4295907,4307251,
4320953,4333726,4345745,4357099,4368127,4381443,4393918,4405618,4416724,4427492,
4444608,4460526,4475477,4489698,4503070,4519477,4534790,4549222,4562954,4575951,
4591795,4606580,4620542,4633801,4646413,4661706,4675988,4689473,4702274,4714477,
4729282,4743148,4756221,4768606,4780451,4794821,4808276,4820985,4832996,4844581,
4858557,4871639,4883959,4895644,4906971,4920601,4933355,4945346,4956769,4967829,
4981078,4993494,5005165,5016303,5027126,5040064,5052151,5063546,5074389,5084970,
5101431,5116842,5131436,5145295,5158330,5174152,5188978,5203052,5216456,5229087,
5244346,5258689,5272273,5285249,5297507,5312261,5326115,5339278,5351804,5363730,
5378048,5391460,5404245,5416390,5427989,5441864,5454907,5467241,5479054,5490370,
5503845,5516543,5528524,5540019,5551100,5564270,5576637,5588334,5599544,5610431,
5623259,5635301,5646688,5657629,5668264,5680733,5692492,5703586,5714304,5724686,
5740568,5755509,5769765,5783154,5795749,5811019,5825429,5839203,5852170,5864428,
5879197,5893125,5906465,5919016,5930950,5945229,5958684,5971571,5983726,5995318,
6009173,6022241,6034731,6046569,6057901,6071352,6084018,6096132,6107639,6118762,
6131845,6144152,6155917,6167148,6178017,6190748,6202765,6214207,6225199,6235854,
6248238,6259936,6271122,6281842,6292282,6304401,6315811,6326727,6337241,6347468,
6362850,6377364,6391270,6404220,6416462,6431293,6445302,6458763,6471348,6483225,
6497539,6511123,6524149,6536365,6547969,6561819,6574923,6587544,6599372,6610705,
6624168,6636874,6649128,6660672,6671740,6684816,6697162,6709022,6720314,6731176,
6743849,6755843,6767401,6778405,6789058,6801426,6813069,6824364,6835105,6845573,
6857599,6868982,6879972,6890536,6900765,6912509,6923628,6934386,6944738,6954793,
6976583,6996285,7014095,7030588,7045942,7066672,7085511,7102619,7118527,7133324,
7153096,7171148,7187588,7202960,7217267,7236173,7253551,7269451,7284339,7298238,
7316346,7333102,7348488,7362912,7376359,7393745,7409939,7424845,7438854,7451901,
7468651,7484336,7498853,7512453,7525188,7541342,7556515,7570617,7583868,7596271,
7611835,7626540,7640228,7653107,7665191,7680213,7694457,7707794,7720323,7732131,
7752829,7771537,7788609,7804493,7819332,7839107,7857044,7873447,7888788,7903158,
7922072,7939289,7955106,7969917,7983801,8001955,8018568,8033854,8048239,8061674,
8079146,8095190,8110000,8123944,8137010,8153844,8169358,8183759,8197305,8209989,
8226256,8241296,8255293,8268482,8280812,8296532,8311160,8324781,8337637,8349662,
8364873,8379035,8392319,8404796,8416558,8431245,8444976,8457899,8470072,8481543,
8501214,8519098,8535530,8550862,8565293,8584112,8601284,8617098,8631916,8645838,
8663896,8680430,8695652,8709973,8723430,8740833,8756791,8771553,8785438,8798508,
8815311,8830751,8845054,8858566,8871242,8887488,8902422,8916325,8929457,8941769,
8957507,8972020,8985565,8998341,9010332,9025589,9039681,9052898,9065355,9077035,
9091800,9105507,9118363,9130510,9141930,9156211,9169498,9182051,9193866,9205050,
9223708,9240868,9256704,9271565,9285593,9303493,9320003,9335273,9349618,9363199,
9380409,9396299,9411040,9424902,9438009,9454621,9470000,9484265,9497747,9510443,
9526527,9541425,9555264,9568346,9580694,9596276,9610699,9624166,9636889,9648877,
9664007,9678043,9691160,9703588,9715239,9729925,9743594,9756386,9768499,9779898,
9794149,9807402,9819898,9831686,9842802,9856617,9869498,9881674,9893214,9904095,
9921920,9938397,9953693,9968116,9981880,9998988,10014875,10029631,10043568,10056856,
10073334,10088643,10102895,10116381,10129221,10145145,10159963,10173779,10186831,10199288,
10214736,10229102,10242501,10255201,10267274,10282245,10296199,10309229,10321576,10333318,
10347900,10361462,10374190,10386204,10397657,10411833,10425034,10437437,10449184,10460350,
10474116,10486974,10499050,10510525,10521428,10534804,10547282,10559107,10570322,10581019,
10598074,10613991,10628824,10642859,10656301,10672739,10688069,10702398,10715968,10728985,
10744812,10759579,10773398,10786514,10799059,10814375,10828695,10842081,10854804,10866960,
10881836,10895746,10908761,10921080,10932932,10947378,10960872,10973539,10985524,10997055,
11011094,11024236,11036544,11048231,11059473,11073146,11085947,11097967,11109367,11120363,
11133713,11146143,11157892,11169032,11179797,11192779,11204881,11216341,11227265,11237788,
11254191,11269585,11284001,11297740,11310752,11326535,11341389,11355287,11368604,11381211,
11396460,11410781,11424209,11437061,11449286,11464064,11477919,11490945,11503371,11515232,
11529591,11543049,11555674,11567757,11579304,11593240,11606330,11618613,11630331,11641607,
11655193,11667918,11679922,11691349,11702365,11715602,11727997,11739665,11750833,11761612,
11774511,11786589,11797968,11808873,11819414,11831994,11843762,11854914,11865605,11875940,
11891709,11906656,11920708,11934148,11946798,11962036,11976447,11990033,12003027,12015315,
12030031,12043940,12057022,12069608,12081517,12095783,12109262,12121935,12134133,12145732,
12159629,12172719,12185034,12196860,12208192,12221682,12234381,12246341,12257893,12268919,
12282050,12294425,12306066,12317326,12328147,12340947,12352977,12364355,12375338,12385962,
12398464,12410178,12421296,12432031,12442408,12454619,12466073,12476902,12487443,12497616,
12512881,12527353,12541137,12554144,12566393,12581112,12595117,12608409,12621021,12632958,
12647192,12660699,12673545,12685745,12697371,12711187,12724276,12736708,12748547,12759893,
12773347,12786075,12798124,12809685,12820745,12833815,12846167,12857891,12869161,12880002,
12892743,12904723,12916175,12927189,12937821,12950227,12961918,12973061,12983858,12994262,
13006355,13017779,13028665,13039220,13049421,13061255,13072394,13083081,13093416,13103432,
13118208,13132276,13145728,13158335,13170250,13184533,13198137,13211156,13223405,13235027,
13248822,13261988,13274520,13286411,13297720,13311112,13323865,13336038,13347603,13358682,
13371747,13384129,13395989,13407262,13418117,13430808,13442814,13454333,13465374,13475977,
13488326,13500029,13511263,13522081,13532516,13544566,13555938,13566939,13577509,13587773,
13599537,13610626,13621368,13631739,13641793,13653298,13664179,13674680,13684846,13694682,
13715445,13734267,13751415,13767294,13782106,13801878,13819928,13836441,13851754,13866076,
13884983,13902362,13918311,13933165,13947004,13965103,13981854,13997313,14011739,14025210,
14042583,14058750,14073727,14087732,14100803,14117512,14133184,14147718,14161347,14174040,
14190134,14205324,14219424,14232672,14245038,14260578,14275326,14289069,14301961,14314021,
14329001,14343280,14356614,14369176,14380947,14395419,14409278,14422249,14434511,14446019,
14465791,14483711,14500177,14515465,14529813,14548726,14565946,14581794,14596564,14610415,
14628564,14645165,14660523,14674847,14688297,14705770,14721809,14736685,14750636,14763678,
14780479,14795996,14810408,14823965,14836624,14852859,14867907,14881928,14895104,14907435,
14923119,14937719,14951365,14964213,14976195,14991343,15005568,15018851,15031393,15043070,
15057705,15071492,15084429,15096609,15108076,15122242,15135609,15148222,15160132,15171368,
15190220,15207384,15223235,15238019,15251961,15270013,15286534,15301812,15316103,15329564,
15346955,15362913,15377701,15391574,15404599,15421399,15436822,15451178,15464665,15477345,
15493571,15508514,15522438,15535557,15547862,15563571,15578103,15591642,15604436,15616379,
15631584,15645701,15658888,15671355,15683003,15697747,15711485,15724381,15736535,15747911,
15762177,15775517,15788053,15799935,15811043,15824853,15837843,15850059,15861682,15872614,
15890538,15907024,15922300,15936647,15950217,15967434,15983311,15998072,16011922,16025027,
16041654,16056991,16071299,16084755,16097440,16113516,16128391,16142250,16155357,16167641,
16183184,16197631,16211097,16223831,16235766,16250869,16264911,16278049,16290446,16302070,
16316718,16330366,16343163,16355271,16366576,16380791,16394117,16406613,16418469,16429517,
16443301,16456244,16468423,16479983,16490838,16504230,16516792,16528691,16540018,16550673,
16567838,16583699,16598483,16612400,16625756,16642250,16657532,16671790,16685245,16698107,
16714047,16728845,16742656,16755720,16768140,16783579,16797939,16811365,16824065,16836156,
16851120,16865056,16878116,16890441,16902159,16916672,16930247,16942941,16954971,16966346,
16980442,16993660,17006057,17017790,17028895,17042636,17055527,17067650,17079144,17089987,
17103312,17115854,17127643,17138920,17149548,17162506,17174723,17186266,17197275,17207734,
17224196,17239530,17253843,17267410,17280452,17296322,17311103,17324932,17338025,17350626,
17365990,17380295,17393682,17406387,17418595,17433471,17447358,17460354,17472712,17484533,
17498957,17512481,17525113,17537112,17548623,17562651,17575790,17588130,17599787,17611005,
17624639,17637428,17649451,17660865,17671766,17685042,17697539,17709272,17720452,17731162,
17744104,17756275,17767754,17778684,17789201,17801810,17813661,17824897,17835647,17845948,
17861810,17876646,17890601,17903888,17916553,17931840,17946169,17959595,17972439,17984678,
17999470,18013351,18026350,18038791,18050685,18065077,18078537,18091173,18103233,18114815,
18128785,18141878,18154145,18165900,18177141,18190692,18203444,18215408,18226883,18237861,
18251072,18263458,18275119,18286315,18297052,18309921,18322026,18333446,18344400,18354881,
18367422,18379226,18390377,18401113,18411412,18423629,18435181,18446118,18456630,18466778,
18482067,18496484,18510055,18523079,18535402,18550157,18564069,18577178,18589739,18601707,
18616018,18629495,18642164,18654336,18665965,18679853,18692963,18705222,18717087,18728405,
18741905,18754638,18766583,18778131,18789194,18802361,18814723,18826354,18837630,18848449,
18861241,18873277,18884623,18895649,18906195,18918653,18930430,18941517,18952308,18962677,
18974851,18986343,18997243,19007778,19017938,19029803,19041055,19051715,19062068,19072027,
19086827,19100793,19114116,19126725,19138702,19152973,19166486,19179295,19191488,19203124,
19216943,19230047,19242437,19254279,19265635,19279094,19291822,19303864,19315391,19326482,
19339580,19351957,19363630,19374910,19385730,19398472,19410526,19421889,19432946,19443553,
19455973,19467689,19478795,19489599,19500013,19512107,19523544,19534431,19545006,19555170,
19566959,19578177,19588825,19599194,19609185,19620739,19631696,19642193,19652345,19662166,
19676499,19690109,19703088,19715335,19727005,19740854,19753996,19766562,19778434,19789801,
19803224,19815970,19828114,19839693,19850772,19863795,19876183,19887954,19899243,19910096,
19922803,19934836,19946313,19957322,19967975,19980377,19992102,20003301,20014122,20024535,
20036573,20048008,20058932,20069555,20079764,20091499,20102659,20113360,20123756,20133785,
20145272,20156182,20166699,20176871,20186696,20197957,20208646,20218955,20229013,20238658,
20258443,20276474,20293012,20308298,20322597,20341515,20358867,20374879,20389689,20403565,
20421696,20438435,20453944,20468322,20481807,20499199,20515368,20530382,20544365,20557471,
20574177,20589807,20604414,20617983,20630756,20646853,20661989,20676155,20689361,20701761,
20717274,20731987,20745746,20758602,20770688,20785688,20799944,20813311,20825817,20837653,
20852142,20865971,20878984,20891179,20902755,20916739,20930188,20942775,20954695,20966010,
20984943,21002118,21018024,21032794,21046638,21064811,21081389,21096764,21111081,21124505,
21141974,21157999,21172928,21186808,21199886,21216716,21232205,21246708,21260205,21272915,
21289141,21304162,21318229,21331393,21343731,21359396,21373960,21387635,21400427,21412464,
21427629,21441774,21455102,21467540,21479291,21493961,21507723,21520686,21532839,21544298,
21558467,21571860,21584470,21596331,21607602,21621310,21634299,21646585,21658154,21669203,
21687307,21703785,21719094,21733379,21746853,21764279,21780185,21795033,21808867,21821937,
21838735,21854138,21868544,21881994,21894655,21910877,21925806,21939795,21952864,21965192,
21980882,21995366,22008994,22021733,22033727,22048923,22062990,22076230,22088633,22100308,
22115033,22128735,22141625,22153714,22165121,22179410,22192762,22205350,22217145,22228315,
22242142,22255124,22267393,22278956,22289922,22303284,22315901,22327830,22339156,22349898,
22367185,22383021,22397784,22411660,22424773,22441419,22456741,22471054,22484503,22497209,
22513301,22528142,22542082,22555121,22567447,22582999,22597396,22610931,22623637,22635611,
22650690,22664678,22677849,22690219,22701850,22716482,22730092,22742926,22754963,22766328,
22780559,22793830,22806368,22818101,22829202,22842997,22855944,22868151,22879665,22890498,
22903873,22916487,22928405,22939669,22950338,22963331,22975586,22987254,22998281,23008770,
23025332,23040600,23054881,23068330,23081223,23097216,23111962,23125826,23138880,23151361,
23166827,23181131,23194599,23207304,23219386,23234352,23248238,23261322,23273649,23285374,
23299903,23313401,23326167,23338160,23349599,23363703,23376870,23389295,23400985,23412111,
23425805,23438661,23450789,23462218,23473093,23486441,23498963,23510842,23522022,23532684,
23545639,23557860,23569448,23580430,23590877,23603442,23615356,23626681,23637463,23647763,
23663684,23678448,23692301,23705412,23718020,23733400,23747691,23761108,23773815,23786035,
23800943,23814784,23827859,23840165,23852041,23866502,23879935,23892615,23904614,23916158,
23930179,23943279,23955621,23967288,23978539,23992177,24004927,24016985,24028334,24039334,
24052609,24065037,24076814,24087921,24098643,24111536,24123704,24135228,24146131,24156609,
24169145,24181011,24192306,24202990,24213314,24225535,24237120,24248152,24258645,24268780,
24284132,24298444,24311934,24324774,24337060,24351925,24365758,24378830,24391269,24403174,
24417579,24431019,24443669,24455758,24467363,24481341,24494387,24506707,24518439,24529756,
24543359,24556062,24568036,24579471,24590507,24603716,24616088,24627767,24638911,24649665,
24662517,24674597,24686051,24696961,24707495,24720025,24731806,24743030,24753721,24764046,
24776226,24787757,24798739,24809226,24819346,24831203,24842497,24853246,24863531,24873479,
24888321,24902193,24915325,24927930,24939873,24954234,24967673,24980376,24992577,25004239,
25018194,25031235,25043606,25055441,25066837,25080389,25093070,25105028,25116564,25127672,
25140852,25153210,25164857,25176098,25186940,25199771,25211781,25223184,25234158,25244759,
25257266,25268986,25280132,25290903,25301271,25313414,25324911,25335824,25346396,25356565,
25368419,25379652,25390361,25400691,25410686,25422265,25433270,25443768,25453901,25463707,
25478072,25491533,25504414,25516628,25528324,25542227,25555262,25567704,25579566,25590933,
25604408,25617079,25629130,25640691,25651802,25664907,25677227,25688966,25700203,25711100,
25723890,25735876,25747310,25758309,25768962,25781369,25793070,25804208,25814988,25825376,
25837468,25848872,25859776,25870327,25880547,25892397,25903556,25914260,25924634,25934669,
25946217,25957180,25967681,25977845,25987687,25998952,26009682,26019975,26029938,26039575,
26053485,26066610,26079170,26091078,26102480,26115969,26128639,26140806,26152366,26163518,
26176612,26188920,26200749,26212033,26222912,26235649,26247619,26259110,26270140,26280781,
26293170,26304840,26316078,26326866,26337314,26349393,26360749,26371713,26382287,26392515,
26404286,26415406,26426121,26436508,26446544,26458035,26468948,26479449,26489649,26499504,
26510759,26521437,26531777,26541783,26551479,26562495,26572971,26583117,26592911,26602369,
26621266,26638678,26654638,26669440,26683245,26701348,26718165,26733646,26748010,26761451,
26778830,26795069,26810094,26824033,26837125,26853835,26869554,26884134,26897724,26910481,
26926567,26941765,26955905,26969099,26981529,26997085,27011794,27025573,27038411,27050529,
27065525,27079810,27093186,27105695,27117492,27131991,27145849,27158874,27171047,27182620,
27196645,27210051,27222705,27234577,27245924,27259484,27272489,27284778,27296374,27307487,
27325637,27342246,27357599,27371903,27385285,27402735,27418818,27433716,27447615,27460604,
27477412,27492956,27507424,27520905,27533591,27549811,27564879,27578970,27592104,27604488,
27620156,27634753,27648419,27661190,27673208,27688357,27702550,27715844,27728276,27740021,
27754702,27768475,27781472,27793575,27805078,27819304,27832688,27845330,27857175,27868454,
27882172,27895158,27907440,27919017,27930034,27943304,27955906,27967856,27979159,27990025,
28007421,28023367,28038157,28052021,28065008,28081802,28097228,28111617,28125057,28137692,
28153903,28168867,28182836,28195927,28208210,28223883,28238409,28252026,28264760,28276739,
28291926,28306017,28319253,28331609,28343294,28358031,28371724,28384639,28396686,28408093,
28422371,28435724,28448295,28460059,28471204,28485066,28498071,28510350,28521861,28532834,
28546271,28558874,28570860,28582095,28592888,28605898,28618151,28629827,28640863,28651439,
28668075,28683409,28697716,28711167,28723827,28739895,28754756,28768641,28781728,28794004,
28809552,28823961,28837479,28850148,28862093,28877178,28891174,28904370,28916716,28928375,
28942995,28956620,28969453,28981458,28992806,29006992,29020267,29032785,29044475,29055572,
29069374,29082303,29094551,29105955,29116819,29130263,29142894,29154857,29166059,29176722,
29189713,29201998,29213663,29224662,29235135,29247758,29259700,29271105,29281861,29292198,
29308159,29322941,29336768,29349866,29362287,29377745,29392070,29405511,29418195,29430277,
29445252,29459145,29472230,29484576,29496277,29510798,29524338,29537081,29549099,29560539,
29574643,29587802,29600233,29611888,29623050,29636775,29649584,29661720,29673107,29683980,
29697311,29709840,29721690,29732825,29743472,29756460,29768703,29780358,29791264,29801754,
29814384,29826285,29837669,29848389,29858678,29870926,29882551,29893660,29904179,29914298,
29929676,29943968,29957390,29970131,29982292,29997172,30011035,30024070,30036438,30048258,
30062711,30076152,30088850,30100809,30112355,30126409,30139498,30151875,30163530,30174775,
30188410,30201167,30213205,30224581,30235534,30248801,30261224,30273003,30284094,30294831,
30307758,30319878,30331435,30342269,30352769,30365370,30377226,30388535,30399196,30409484,
30421709,30433313,30444386,30454859,30464981,30476902,30488220,30499097,30509358,30519347,
30534184,30548038,30561093,30573588,30585451,30599841,30613274,30625960,30638056,30649620,
30663573,30676617,30688929,30700676,30711925,30725494,30738196,30750176,30761607,30772617,
30785855,30798225,30809944,30821076,30831849,30844722,30856770,30868228,30879116,30889653,
30902178,30913940,30925143,30935793,30946123,30958350,30969890,30980916,30991357,31001498,
31013426,31024697,31035497,31045765,31055711,31067302,31078367,31088960,31099045,31108837,
31123226,31136670,31149379,31161650,31173242,31187160,31200204,31212526,31224445,31235760,
31249292,31261945,31273942,31285469,31296547,31309744,31322046,31333740,31344998,31355812,
31368635,31380652,31392017,31403020,31413586,31426081,31437794,31448928,31459662,31470052,
31482254,31493697,31504623,31515138,31525303,31537227,31548480,31559193,31569520,31579509,
31591110,31602128,31612662,31622772,31632605,31643963,31654731,31665099,31675011,31684643,
31698552,31711588,31724024,31735936,31747292,31760800,31773445,31785514,31797117,31808192,
31821302,31833579,31845292,31856613,31867425,31880185,31892127,31903575,31914581,31925208,
31937673,31949303,31960491,31971231,31981642,31993789,32005157,32016073,32026621,32036810,
32048654,32059820,32070518,32080834,32090863,32102454,32113396,32123923,32134063,32143901,
32155232,32165969,32176290,32186263,32195905,32206973,32217532,32227673,32237462,32246926,
32260417,32273125,32285275,32296898,32307990,32321091,32333387,32345206,32356546,32367418,
32380160,32392077,32403605,32414661,32425302,32437701,32449286,32460507,32471332,32481722,
32493792,32505130,32516088,32526674,32536891,32548689,32559775,32570525,32580874,32590908,
32602443,32613285,32623840,32633998,32643839,32655119,32665803,32676142,32686130,32695804,
32706851,32717320,32727484,32737279,32746742,32757589,32767849,32777867,32787489,32796782,
32814880,32831723,32847182,32861562,32874968,32892314,32908592,32923576,32937516,32950587,
32967287,32983056,32997620,33011185,33023953,33040032,33055320,33069457,33082689,33095113,
33110602,33125420,33139116,33152004,33164127,33179106,33193430,33206772,33219316,33231148,
33245646,33259527,33272493,33284746,33296316,33310319,33323763,33336348,33348271,33359587,
33373156,33386160,33398405,33410029,33421118,33434234,33446795,33458691,33470054,33480907,
33498345,33514419,33529316,33543201,33556228,33573030,33588613,33603070,33616571,33629225,
33645412,33660544,33674578,33687732,33700084,33715702,33730398,33744062,33756838,33768904,
33784018,33798263,33811563,33824024,33835776,33850393,33864228,33877142,33889314,33900799,
33914973,33928409,33940964,33952831,33964089,33977828,33990851,34003113,34014703,34025744,
34039049,34051684,34063592,34074950,34085770,34098583,34110822,34122425,34133513,34144108,
34160883,34176351,34190701,34204189,34216817,34233000,34247987,34261927,34275004,34287282,
34302937,34317502,34331072,34343813,34355794,34370928,34385102,34398329,34410741,34422414,
34437075,34450845,34463706,34475787,34487205,34501433,34514814,34527350,34539135,34550325,
34564162,34577182,34589389,34600931,34611889,34625303,34637998,34649897,34661191,34671945,
34684949,34697227,34708874,34719928,34730521,34743095,34755002,34766343,34777188,34787529,
34803596,34818475,34832365,34845427,34857718,34873249,34887703,34901194,34913897,34925813,
34940837,34954901,34968041,34980410,34992032,35006616,35020279,35033109,35045134,35056488,
35070638,35083938,35096412,35108153,35119231,35132964,35145937,35158084,35169573,35180431,
35193815,35206472,35218352,35229559,35240221,35253233,35265536,35277163,35288156,35298620,
35311237,35323233,35334568,35345370,35355655,35367853,35379514,35390621,35401206,35411317,
35426732,35441115,35454560,35467282,35479293,35494213,35508175,35521271,35533604,35545295,
35559791,35573351,35586112,35598133,35609550,35623598,35636825,35649233,35660957,35672064,
35685719,35698589,35710681,35722105,35732999,35746315,35758855,35770670,35781824,35792513,
35805466,35817732,35829281,35840225,35850682,35863275,35875245,35886564,35897296,35907566,
35919820,35931483,35942589,35953121,35963231,35975125,35986477,35997311,36007667,36017597,
36032475,36046372,36059450,36071824,36083617,36098003,36111500,36124188,36136193,36147675,
36161653,36174796,36187164,36198859,36210061,36223667,36236453,36248505,36259917,36270874,
36284116,36296597,36308331,36319477,36330182,36343046,36355230,36366688,36377581,36388092,
36400652,36412552,36423822,36434468,36444784,36457033,36468672,36479730,36490220,36500333,
36512227,36523599,36534418,36544733,36554676,36566259,36577336,36587940,36598027,36607817,
36622169,36635651,36648345,36660512,36671993,36685902,36698980,36711328,36723098,36734324,
36747877,36760598,36772608,36784091,36795077,36808240,36820657,36832351,36843546,36854284,
36867110,36879205,36890622,36901532,36912058,36924560,36936380,36947571,36958244,36968561,
36980755,36992339,37003304,37013803,37023907,37035786,37047110,37057891,37068184,37078147,
37089756,37100825,37111411,37121519,37131327,37142648,37153464,37163802,37173723,37183292,
37197223,37210290,37222656,37234580,37245833,37259329,37272039,37284008,37295641,37306604,
37319718,37332079,37343753,37355065,37365847,37378643,37390678,37402066,37413076,37423645,
37436093,37447865,37458984,37469765,37480077,37492186,37503701,37514596,37525130,37535283,
37547159,37558417,37569155,37579470,37589462,37601072,37612118,37622631,37632794,37642603,
37653942,37664785,37675095,37685074,37694729,37705803,37716394,37726520,37736282,37745713,
37759182,37771885,37783967,37795610,37806644,37819735,37832028,37843773,37855101,37865914,
37878654,37890635,37902056,37913119,37923694,37936073,37947750,37958895,37969705,37980059,
37992147,38003568,38014482,38025038,38035222,38047017,38058195,38068897,38079237,38089202,
38100729,38111695,38122178,38132352,38142136,38153461,38164236,38174542,38184511,38194179,
38205286,38215865,38225986,38235791,38245263,38256079,38266450,38276374,38285979,38295232,
38308315,38320652,38332491,38343883,38354701,38367397,38379374,38390856,38401963,38412552,
38424890,38436529,38447750,38458594,38468981,38481033,38492376,38503334,38513954,38524132,
38535871,38546969,38557705,38568108,38578081,38589540,38600402,38610936,38621127,38630964,
38642231,38652895,38663236,38673224,38682866,38693899,38704390,38714542,38724381,38733828,
38744654,38754988,38764959,38774610,38783911,38794522,38804637,38814416,38823828,38832914,
38850330,38866580,38881569,38895473,38908583,38925334,38941063,38955594,38969144,38981897,
38998010,39013256,39027387,39040565,39053029,39068626,39083433,39097168,39110043,39122221,
39137240,39151575,39164892,39177438,39189297,39203819,39217716,39230638,39242857,39254476,
39268516,39281977,39294556,39306471,39317805,39331390,39344435,39356648,39368342,39379416,
39392515,39405096,39416936,39428324,39439158,39451847,39464036,39475610,39486732,39497335,
39514162,39529700,39544141,39557576,39570288,39586532,39601597,39615639,39628749,39641115,
39656791,39671444,39685080,39697856,39709901,39725061,39739307,39752597,39765064,39776869,
39791541,39805349,39818257,39830396,39841927,39856125,39869577,39882122,39893988,39905236,
39918950,39932013,39944190,39955811,39966831,39980157,39992811,40004705,40016061,40026905,
40039774,40051986,40063562,40074680,40085269,40097693,40109589,40120863,40131750,40142121,
40158340,40173313,40187268,40200321,40212631,40228316,40242861,40256416,40269123,40281128,
40296313,40310436,40323641,40336013,40347739,40362484,40376242,40389109,40401203,40412657,
40426904,40440292,40452805,40464603,40475820,40489642,40502676,40514865,40526369,40537361,
40550773,40563443,40575304,40586592,40597348,40610365,40622704,40634274,40645371,40655927,
40668504,40680468,40691752,40702596,40712973,40725160,40736790,40747843,40758480,40768651,
40784194,40798637,40812165,40824799,40836794,40851868,40865886,40879033,40891363,40903033,
40917633,40931302,40944064,40956085,40967460,40981644,40994969,41007421,41019142,41030286,
41044066,41057025,41069170,41080640,41091552,41104921,41117581,41129404,41140649,41151325,
41164300,41176627,41188162,41199161,41209639,41222298,41234328,41245644,41256427,41266742,
41278987,41290666,41301710,41312303,41322423,41334288,41345706,41356495,41366906,41376852,
41391786,41405718,41418833,41431167,41442902,41457406,41470962,41483713,41495680,41507137,
41521220,41534412,41546829,41558492,41569660,41583358,41596236,41608330,41619751,41630662,
41643952,41656523,41668305,41679473,41690170,41703128,41715363,41726910,41737842,41748361,
41760970,41772933,41784183,41794921,41805197,41817447,41829178,41840178,41850747,41860855,
41872750,41884163,41894950,41905288,41915224,41926820,41937952,41948551,41958730,41968476,
41982900,41996385,42009141,42021079,42032593,42046600,42059727,42072111,42083773,42095005,
42108580,42121382,42133423,42144788,42155775,42168997,42181495,42193243,42204327,42215075,
42227967,42240135,42251618,42262507,42273030,42285566,42297484,42308706,42319407,42329738,
42341952,42353590,42364575,42375037,42385199,42397127,42408519,42419310,42429587,42439557,
42451173,42462306,42472852,42482978,42492725,42504012,42514913,42525255,42535218,42544806,
42558753,42571838,42584193,42595951,42607199,42620738,42633481,42645528,42656959,42667971,
42681140,42693529,42705260,42716403,42727171,42739987,42752091,42763519,42774417,42784944,
42797409,42809257,42820435,42831123,42841453,42853637,42865219,42876192,42886669,42896829,
42908700,42920057,42930771,42941060,42951025,42962628,42973771,42984287,42994401,43004191,
43015506,43026393,43036726,43046644,43056253,43067323,43077965,43088108,43097882,43107279,
43120817,43133517,43145579,43157106,43168113,43181257,43193635,43205331,43216607,43227382,
43240129,43252186,43263593,43274585,43285164,43297601,43309346,43320506,43331240,43341612,
43353750,43365244,43376150,43386674,43396821,43408648,43419965,43430648,43440990,43450971,
43462554,43473620,43484121,43494233,43504065,43515423,43526283,43536600,43546570,43556222,
43567267,43577916,43587991,43597783,43607184,43617993,43628442,43638350,43647923,43657184,
43670267,43682584,43694338,43705611,43716428,43729154,43741158,43752622,43763624,43774223,
43786599,43798275,43809464,43820255,43830647,43842692,43854111,43865011,43875572,43885764,
43897502,43908684,43919370,43929688,43939671,43951188,43962162,43972663,43982810,43992660,
44003946,44014768,44025045,44035012,44044641,44055669,44066280,44076386,44086186,44095641,
44106477,44116859,44126779,44136356,44145637,44156235,44166441,44176173,44185553,44194636,
44207330,44219288,44230851,44241883,44252494,44264834,44276495,44287749,44298580,44308986,
44320959,44332331,44343304,44353890,44364108,44375807,44386881,44397632,44407986,44418014,
44429471,44440340,44450852,44461042,44470872,44482082,44492776,44503097,44513087,44522725,
44533709,44544211,44554357,44564164,44573633,44584424,44594755,44604718,44614363,44623628,
44634173,44644340,44654092,44663523,44672601,44682952,44692935,44702487,44711720,44720629,
44737428,44753119,44767673,44781230,44794005,44810203,44825415,44839524,44852743,44865198,
44880825,44895579,44909314,44922178,44934349,44949459,44963743,44977142,44989674,45001584,
45016183,45030056,45043050,45055279,45066911,45080979,45094409,45107026,45118960,45130333,
45143948,45156933,45169192,45180832,45191976,45205145,45217683,45229566,45240916,45251787,
45264505,45276688,45288274,45299390,45310025,45322377,45334196,45345536,45356407,45366844,
45383129,45398195,45412203,45425310,45437696,45453436,45468044,45481675,45494454,45506553,
45521805,45535980,45549271,45561755,45573530,45588255,45602061,45614978,45627148,45638699,
45652946,45666329,45678950,45690805,45702135,45715910,45728888,45741142,45752751,45763831,
45777152,45789756,45801665,45813024,45823880,45836758,45848961,45860555,45871618,45882265,
45894772,45906599,45917918,45928765,45939191,45951277,45962846,45973920,45984590,45994799,
46010532,46025063,46038633,46051322,46063347,46078580,46092690,46105870,46118246,46129966,
46144757,46158473,46171330,46183392,46194870,46209203,46222537,46235086,46246890,46258127,
46272011,46284992,46297213,46308762,46319762,46333206,46345802,46357699,46369002,46379779,
46392812,46405062,46416682,46427732,46438321,46450947,46462851,46474162,46484978,46495363,
46507557,46519155,46530213,46540829,46551000,46562880,46574180,46585029,46595437,46605449,
46620531,46634581,46647723,46660000,46671687,46686344,46699982,46712786,46724754,46736169,
46750404,46763714,46776176,46787904,46799035,46812845,46825807,46837954,46849422,46860364,
46873797,46886366,46898255,46909470,46920203,46933267,46945502,46957086,46968087,46978609,
46991258,47003223,47014534,47025330,47035651,47047925,47059549,47070609,47081155,47091288,
47103217,47114547,47125392,47135752,47145705,47157282,47168396,47179009,47189223,47198975,
47213513,47227091,47239875,47251811,47263262,47277362,47290583,47303016,47314675,47325865,
47339593,47352475,47364591,47375973,47386941,47400309,47412833,47424665,47435839,47446554,
47459550,47471786,47483323,47494306,47504820,47517457,47529373,47540665,47551406,47561735,
47574054,47585683,47596749,47607275,47617432,47629374,47640752,47651560,47661892,47671839,
47683446,47694523,47705134,47715277,47725059,47736399,47747256,47757664,47767643,47777248,
47791270,47804415,47816833,47828438,47839686,47853319,47866096,47878185,47889497,47900480,
47913749,47926219,47938004,47949101,47959851,47972770,47984925,47996452,48007314,48017897,
48030505,48042360,48053632,48064291,48074653,48086921,48098515,48109519,48119992,48130154,
48142096,48153464,48164263,48174557,48184527,48196185,48207280,48217881,48227977,48237785,
48249141,48259994,48270370,48280320,48289914,48300973,48311609,48321777,48331576,48340949,
48354547,48367303,48379381,48390757,48401734,48414907,48427327,48439062,48450171,48460940,
48473803,48485885,48497359,48508219,48518784,48531326,48543144,48554367,48565036,48575385,
48587586,48599165,48610128,48620603,48630774,48642683,48653995,48664754,48675004,48684983,
48696637,48707710,48718297,48728367,48738184,48749533,48760390,48770728,48780661,48790253,
48801330,48811948,48822106,48831839,48841257,48852121,48862534,48872512,48882062,48891281,
48904462,48916853,48928610,48939775,48950568,48963397,48975450,48986906,48997835,49008406,
49020873,49032628,49043803,49054519,49064893,49077066,49088573,49099506,49109978,49120186,
49132093,49143357,49154103,49164387,49174403,49186020,49197079,49207579,49217694,49227508,
49238849,49249693,49260025,49269961,49279587,49290701,49301295,49311447,49321204,49330650,
49341542,49351972,49361902,49371510,49380748,49391361,49401573,49411342,49420708,49429749,
49442507,49454521,49466036,49477019,49487593,49499983,49511671,49522866,49533591,49544003,
49556111,49567529,49578474,49588966,49599175,49610986,49622177,49632908,49643212,49653214,
49664780,49675759,49686271,49696407,49706263,49717565,49728321,49738662,49748580,49758231,
49769307,49779874,49790026,49799805,49809251,49820105,49830481,49840417,49850000,49859258,
49869887,49880068,49889845,49899225,49908319,49918766,49928768,49938344,49947525,49956416,
49968790,49980424,49991756,50002516,50012939,50024980,50036330,50047354,50057891,50068106,
50079817,50090931,50101698,50112022,50122054,50133523,50144402,50154968,50165071,50174919,
50186164,50196835,50207203,50217183,50226849,50237853,50248353,50258482,50268317,50277769,
50288572,50298870,50308843,50318465,50327748,50338342,50348468,50358261,50367672,50376753,
50387160,50397107,50406698,50415932,50424815,50435003,50444804,50454175,50463196,50471934,
50488091,50503290,50517354,50530592,50543022,50558620,50573354,50587064,50599984,50612052,
50627117,50641400,50654715,50667322,50679125,50693710,50707553,50720565,50732849,50744445,
50758526,50771929,50784562,50796534,50807863,50821460,50834450,50846693,50858361,50869439,
50882575,50895111,50907024,50918353,50929201,50941960,50954094,50965705,50976803,50987429,
50999791,51011602,51022922,51033806,51044220,51056218,51067703,51078779,51089395,51099607,
51115294,51129928,51143509,51156337,51168361,51183546,51197732,51210970,51223454,51235216,
51249942,51263701,51276604,51288806,51300300,51314549,51327939,51340524,51352481,51363750,
51377533,51390485,51402728,51414346,51425403,51438739,51451292,51463245,51474593,51485421,
51498303,51510469,51522085,51533174,51543742,51556219,51568035,51579371,51590216,51600619,
51612735,51624249,51635338,51645976,51656190,51667975,51679200,51690043,51700466,51710497,
51725689,51739783,51752957,51765345,51777039,51791780,51805514,51818332,51830463,51841877,
51856180,51869520,51882003,51893848,51905040,51918941,51931913,51944119,51955710,51966703,
51980167,51992736,52004649,52015986,52026746,52039774,52051990,52063593,52074695,52085255,
52097849,52109679,52121013,52131843,52142191,52154450,52165956,52177047,52187660,52197819,
52209726,52221005,52231850,52242270,52252283,52263852,52274860,52285487,52295690,52305518,
52320106,52333768,52346532,52358575,52369942,52384135,52397405,52409847,52421581,52432732,
52446543,52459455,52471573,52483055,52493946,52507369,52519967,52531805,52543104,52553782,
52566827,52579049,52590645,52601669,52612187,52624859,52636708,52648055,52658877,52669180,
52681453,52692982,52704015,52714626,52724716,52736651,52747925,52758753,52769120,52779054,
52790694,52801708,52812349,52822511,52832283,52843610,52854420,52864835,52874839,52884417,
52898510,52911730,52924125,52935820,52946983,52960685,52973581,52985650,52997106,53008002,
53021330,53033890,53045680,53056859,53067584,53080592,53092806,53104370,53115339,53125847,
53138486,53150389,53161672,53172444,53182737,53195031,53206630,53217688,53228261,53238405,
53250379,53261645,53272472,53282817,53292758,53304435,53315459,53326051,53336210,53345986,
53357346,53368182,53378583,53388544,53398129,53409222,53419802,53430047,53439839,53449198,
53462822,53475652,53487666,53499035,53510010,53523290,53535766,53547520,53558634,53569397,
53582333,53594504,53605995,53616885,53627408,53639988,53651881,53663127,53673833,53684177,
53696439,53708030,53719046,53729537,53739690,53751678,53762980,53773792,53784109,53794086,
53805748,53816790,53827343,53837483,53847263,53858640,53869466,53879821,53889755,53899332,
53910468,53921057,53931265,53941023,53950433,53961309,53971695,53981698,53991307,54000471,
54013703,54026145,54037820,54048970,54059725,54072566,54084718,54096139,54107042,54117567,
54130078,54141910,54153097,54163776,54174125,54186362,54197908,54208889,54219384,54229534,
54241448,54252755,54263502,54273807,54283787,54295436,54306493,54317032,54327156,54336960,
54348350,54359129,54369493,54379417,54389024,54400178,54410765,54420925,54430689,54440074,
54450947,54461344,54471313,54480896,54490073,54500710,54510870,54520684,54530072,54539065,
54551857,54563968,54575364,54586292,54596858,54609349,54621135,54632271,54642977,54653321,
54665497,54677040,54687943,54698464,54708606,54720463,54731748,54742447,54752787,54762796,
54774427,54785441,54795950,54806063,54815894,54827266,54838088,54848380,54858347,54867984,
54879093,54889707,54899805,54909588,54919003,54929901,54940270,54950237,54959802,54969042,
54979715,54989868,54999646,55009027,55018064,55028532,55038543,55048108,55057296,55066115,
55078541,55090276,55101423,55112160,55122511,55134575,55146057,55156957,55167480,55177648,
55189447,55200661,55211354,55221685,55231720,55243305,55254268,55264771,55274902,55284761,
55296076,55306840,55317118,55327074,55336740,55347855,55358418,55368528,55378311,55387782,
55398668,55409007,55418939,55428507,55437779,55448448,55458609,55468389,55477782,55486799,
55497233,55507214,55516798,55525984,55534858,55545102,55554888,55564253,55573243,55581915,
55593935,55605330,55616335,55626898,55637110,55648853,55659969,55670710,55681083,55691089,
55702554,55713457,55723957,55734114,55743955,55755188,55765888,55776204,55786186,55795845,
55806884,55817361,55827518,55837308,55846788,55857618,55867939,55877892,55887523,55896814,
55907421,55917530,55927290,55936710,55945777,55956202,55966117,55975719,55984918,55993821,
56004071,56013825,56023215,56032267,56040967,56050996,56060568,56069759,56078589,56087100,
56102658,56117391,56131083,56143982,56156071,56171131,56185403,56198735,56211325,56223092,
56237634,56251511,56264484,56276797,56288279,56302329,56315774,56328409,56340418,56351665,
56365246,56378242,56390520,56402222,56413249,56426335,56438937,56450858,56462278,56473056,
56485728,56497910,56509506,56520629,56531247,56543563,56555395,56566720,56577585,56587992,
56599960,56611498,56622552,56633206,56643393,56655039,56666330,56677136,56687579,56697604,
56712779,56726975,56740204,56752705,56764416,56779099,56792889,56805788,56817985,56829445,
56843673,56857046,56869632,56881564,56892787,56906560,56919562,56931816,56943497,56954471,
56967765,56980372,56992294,57003723,57014495,57027322,57039512,57051120,57062247,57072818,
57085246,57097093,57108421,57119319,57129649,57141697,57153255,57164317,57174994,57185152,
57196851,57208128,57218961,57229378,57239377,57250815,57261813,57272438,57282669,57292496,
57307216,57320919,57333749,57345853,57357282,57371560,57384896,57397378,57409206,57420361,
57434204,57447218,57459407,57471041,57481948,57495376,57508006,57519908,57531287,57542029,
57555031,57567258,57578874,57589988,57600539,57613097,57624964,57636293,57647177,57657469,
57669637,57681201,57692269,57702919,57713058,57724912,57736193,57747062,57757486,57767453,
57778952,57789981,57800601,57810838,57820606,57831826,57842648,57853049,57863107,57872728,
57886919,57900221,57912638,57924413,57935511,57949272,57962218,57974333,57985827,57996697,
58010099,58022684,58034555,58045821,58056498,58069500,58081804,58093374,58104472,58114926,
58127515,58139438,58150745,58161603,58171898,58184122,58195691,58206760,58217383,58227468,
58239347,58250645,58261449,58271876,58281754,58293305,58304366,58314974,58325221,58334967,
58346259,58357049,58367486,58377485,58387038,58398061,58408635,58418880,58428722,58438097,
58451831,58464721,58476771,58488211,58499132,58512481,58525036,58536824,58548042,58558706,
58571665,58583926,58595462,58606465,58616928,58629536,58641463,58652771,58663561,58673870,
58686134,58697765,58708836,58719438,58729547,58741443,58752764,58763572,58773959,58783867,
58795458,58806511,58817087,58827276,58837026,58848369,58859196,58869604,58879605,58889151,
58900196,58910809,58921008,58930849,58940211,58951013,58961414,58971444,58981081,58990253,
59003538,59016074,59027771,59038906,59049654,59062566,59074758,59086212,59097099,59107613,
59120205,59132084,59143329,59154048,59164359,59176596,59188243,59199242,59209776,59219899,
59231808,59243165,59253955,59264305,59274282,59285892,59296959,59307525,59317651,59327409,
59338751,59349592,59359937,59369896,59379443,59390528,59401161,59411329,59421142,59430529,
59441381,59451777,59461808,59471383,59480562,59491178,59501377,59511230,59520655,59529673,
59542572,59554742,59566130,59577021,59587580,59600127,59611979,59623106,59633828,59644141,
59656348,59667952,59678876,59689385,59699522,59711465,59722777,59733540,59743858,59753844,
59765496,59776593,59787134,59797292,59807078,59818393,59829262,59839577,59849539,59859126,
59870200,59880807,59890939,59900700,59910056,59920926,59931324,59941316,59950922,59960092,
59970724,59980937,59990710,60000125,60009102,60019514,60029544,60039175,60048389,60057199,
60069690,60081547,60092597,60103325,60113684,60125860,60137425,60148289,60158811,60168991,
60180887,60192192,60202838,60213177,60223138,60234739,60245832,60256282,60266437,60276243,
60287614,60298481,60308771,60318761,60328395,60339505,60350120,60360233,60370014,60379431,
60390261,60400669,60410584,60420168,60429373,60440023,60450222,60459991,60469374,60478378,
60488831,60498833,60508443,60517642,60526472,60536715,60546556,60555962,60565009,60573660,
60585774,60597272,60608133,60618662,60628848,60640663,60651898,60662527,60672875,60682884,
60694440,60705453,60715905,60726019,60735882,60747191,60757983,60768270,60778233,60787876,
60798968,60809582,60819675,60829489,60838961,60849776,60860173,60870072,60879687,60888926,
60899536,60909709,60919462,60928836,60937892,60948322,60958315,60967883,60977097,60985975,
60996213,61006032,61015403,61024401,61033028,61043079,61052711,61061932,61070742,61079255,
61090990,61102173,61112857,61123220,61133247,61144724,61155656,61166147,61176315,61186172,
61197425,61208148,61218431,61228440,61238101,61249084,61259619,61269701,61279502,61288972,
61299790,61310110,61320071,61329701,61338974,61349578,61359688,61369459,61378887,61387988,
61398378,61408344,61417873,61427101,61435986,61446206,61455977,61465338,61474367,61483093,
61493120,61502707,61511888,61520709,61529229,61539100,61548504,61557500,61566191,61574510
};
int f(int x)
{
if(x==0) return 0;
return f(x/10)+x%10;
}
int main()
{
int cas,k,i,n,m,nn,nm,k1,k2;
scanf("%d",&cas);
for(k=1;k<=cas;k++)
{
scanf("%d %d",&n,&m);
n=n-1;
k1=n/200000;
k2=m/200000;
nn=a[k1];
nm=a[k2];
for(i=k1*200000+1;i<=n;i++)
if(i%f(i)==0) nn++;
for(i=k2*200000+1;i<=m;i++)
if(i%f(i)==0) nm++;
printf("Case %d: %d
",k,nm-nn);
}
return 0;
}
打表コード:
#include
int f (int x)
{
if(x==0) return 0;
return f(x/10)+x%10;
}
int main()
{
int i,cnt=0,num=0,cnt2=0;
freopen("d://521.in","w",stdout);
for(i=1;i<=1000000000;i++)
{
if(i%f(i)==0){cnt++;}
if(i%200000==0)
{
printf("%d,",cnt);
cnt2++;
if(cnt2==10) {printf("
");cnt2=0;}
}
}
return 0;
}
注意長さ1000のテーブルタイムアウト 長さ10000のテーブル制限コード長はコミットされません 5000でちょうどいいです