2010-1160

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<blockquote><p>
将一个数字的相邻两位的差（的绝对值）组成一个新的数字，不断重复，如果最后得到7，就称这个数为July Number，比如9024 – 922 – 70 – 7。题目要求1e9范围内给定区间[a, b]里July Number的个数。

</p></blockquote>
<p>
没有发现这种数字有什么特别的统计上的规律。不过可以想到，这种数是不太多的，事实上对各种Number有<br>
</p><center><br>
<table>
<tbody><tr>
<td></td>
<td>353008254</td>
</tr>
<tr>
<td>January</td>
<td>451156127</td>
</tr>

<tr>
<td>February</td>
<td>131145647</td>
</tr>
<tr>
<td>March</td>
<td>44286220</td>
</tr>
<tr>
<td>April</td>
<td>14800278</td>

</tr>
<tr>
<td>May</td>
<td>4397180</td>
</tr>
<tr>
<td>June</td>
<td>1031969</td>
</tr>
<tr>
<td>July</td>
<td>160218</td>

</tr>
<tr>
<td>August</td>
<td>13851</td>
</tr>
<tr>
<td>September</td>
<td>256</td>
</tr>
<tr>
<td>October</td>
<td>0</td>

</tr>
<tr>
<td>November</td>
<td>0</td>
</tr>
<tr>
<td>December</td>
<td>0</td>
</tr>
</tbody></table>
<p></p></center><br>
所以只要把这些数暴力出来存在一张表里，然后对每个查询做两次二分就能得到答案。生成表的方法就是<strong style="color: rgb(240, 43, 136);">逆推</strong>！比如由7出发，可以得到70, 81, 92, 19, 29，从19出发可以得到109, 890，这只要枚举最后以为数字，然后枚举相邻两位的差是正的还是负的，可以简单的写成一个dfs。


}}}
http://watashi.ws/blog/1622/zojmonthly1011/ZOJ3436/

将一个数字的相邻两位的差（的绝对值）组成一个新的数字，不断重复，如果最后得到7，就称这个数为July Number，比如9024 – 922 – 70 – 7。题目要求1e9范围内给定区间[a, b]里July Number的个数。

没有发现这种数字有什么特别的统计上的规律。不过可以想到，这种数是不太多的，事实上对各种Number有

	353008254
January	451156127
February	131145647
March	44286220
April	14800278
May	4397180
June	1031969
July	160218
August	13851
September	256
October	0
November	0
December	0

所以只要把这些数暴力出来存在一张表里，然后对每个查询做两次二分就能得到答案。生成表的方法就是逆推！比如由7出发，可以得到70, 81, 92, 19, 29，从19出发可以得到109, 890，这只要枚举最后以为数字，然后枚举相邻两位的差是正的还是负的，可以简单的写成一个dfs。

http://watashi.ws/blog/1622/zojmonthly1011/ZOJ3436/