Divisor

陈老师是个热爱数论的少女。
她称n为k-可表达的当且仅当这个数n能被表示n的k个因子之和,注意这些因子可以相同。
她想求在A和B之间有多少k-可表达数,A和B之间包括A和B。
Input
第一行一个整数T表示数据总数。 接下来T行每行三个正整数A, B, K。
Output
一共T行,对于每个询问输出答案。
Constraints
对于10%的数据,有$$T \leq 5$$, $$K \leq 2$$, $$A, B \leq 10^6$$。
对于30%的数据,有$$T \leq 50$$, $$K \leq 4$$, $$A, B \leq 10^6$$。
对于50%的数据,有$$T \leq 500$$, $$K \leq 5$$, $$A, B \leq 10^9$$。
对于70%的数据,有$$T \leq 5000$$,$$K \leq 6$$, $$A, B \leq 10^{12}$$。
对于100%的数据,有$$T \leq t \times 10^4$$, $$2 \leq K \leq 7$$,$$1 \leq A \leq B \leq 10^{18}$$。
Example
divisor.in divisor.out
3 2
1 5 3 3
5 10 2 2
4 6 4

任何一种拆分方式可以写成比如:$$1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$$的形式. 容易看出这个时候只要数是6的倍数就可以了. 先通过暴搜计算一下1拆分7个自然数倒数和的方案. 就能得到一系列数. 问题就转化成了询问$$[l,r]$$中有多少数至少是其中一个的倍数, 经典问题,容斥就可以解决了.

陈老师的代码,然而在OJ上T了,似乎是读入的锅
此条目发表在JCYZOJ, 容斥原理分类目录,贴了标签。将固定链接加入收藏夹。