《怎样解题:数学竞赛攻关宝典(第3版)》第 241 页:

题7.5.12   (普特南 1983) 共有多少个正整数 n,使得 n 是 1040 或 2030 中至少一个数的因数。


回顾本书第 224 页:

题7.3.3 注意 σ0 等于 n 的因数的个数。这个函数一般用 d(n) 来表示。你曾在第 185 页题 6.1.21 和 3.1 节第 64 页见到过它。回忆一下:如果

是 n 的素数幂分解,那么

d(n)=(e1+1)(e2+1)…(et+1)

由这个公式,可以推断出 d(n) 是积性函数。

由容斥原理(见本书 6.3 节),题 7.5.12 的答案是:

d(1040) + d(2030) - d(gcd(1040, 2030) )

= d(240540) + d(260530) - d(240530)

= 41 x 41 + 61 x 31 - 41 x 31

= 2301