试题 A: 门牌制作
问题描述
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字
符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、 0、 1、 7，即需要 1 个
字符 0， 2 个字符 1， 1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2/p>
直接暴力
试题 B: 既约分数
【问题描述】
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如， 3 4 , 5 2 , 1 8 , 7 1 frac{3}{4}, frac{5}{2}, frac{1}{8}, frac{7}{1} 43?,25?,81?,17?都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1
和 2020）/p>
显然这不是一道简单题，我们写下数学式子来
∑ i = 1 n ∑ j = 1 n [ g c d ( i , j ) = 1 ] ∑ k = 1 n μ ( k ) ∑ i = 1 n k ∑ j = 1 n k sum_{i = 1} ^{n} sum_{j = 1} ^{n} [gcd(i, j) = 1]\ sum_{k = 1} ^{n} mu(k) sum_{i = 1} ^{frac{n}{k}} sum_{j = 1} ^{frac{n}{k}}\ i=1∑n?j=1∑n?[gcd(i,j)=1]k=1∑n?μ(k)i=1∑kn??j=1∑kn??
然后就只要线性筛，加数论分块即可。
来源：_lifehappy_
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！
