打飞机
Time Limit: 1s, Memory Limit: 128MB
背景
机房历2817年, 农民 (Famer Tao) 经过长期努力务农, 终于拥有了辽阔无边的农田, 被人们尊称为”农民之王”。
农民之王可不是那么好当, Famer Tao除了每天需要每天辛勤耕耘农田以外, 还要抵御蝗虫獾猪等物种的入侵。
这天, 何老师 (Miracle) 发现了这一片肥沃的农田, 于是派出大量轰炸机准备轰炸农民的领土, 让农民屈服割让农田。
“农民之王” Famer Tao可是那么好惹的! 处于众所周知的原因, 农民对打飞机特别敏感, 在这个领域有着深入的研究和高
潮
超的科技。
Miracle派出的战斗机被Famer Tao的”超级无敌全自动激光发生器”识别成了[latex][L, R][/latex]中的一个整数, 每个区间内整数都恰好对应一架飞机。激光器的运作方式非常独特, 它会随机在[latex][L, R][/latex]中不重复地选择[latex]K[/latex]个整数, 然后会发出一道激光击落这[latex]K[/latex]个整数最大公约数架飞机。
Famer发现Miracle竟然已经知道怎么预测激光器的期望击落数量, 于是他自然就想你求助了。
题目描述
给出Miracle战斗机编号左右端点[latex]L[/latex]和[latex]R[/latex], 以及激光武器的参数K, 问从区间[latex][L, R][/latex]内随机不重复地选择K个整数的期望最大公约数值。
输入格式
一行三个整数L, R, K, 整数之间以单个空格隔开
输出格式
你需要输出一个分数[latex]\frac{a}{b} \pmod{19260817}[/latex]作为
一个真正的粉丝的
答案, 你可以将其理解为[latex]a \times b^{-1} \pmod{19260817}[/latex]。
数据范围与约定
对于 100% 的数据, 有[latex]1 \le L \le R \le 10^6, 1 \le K \le R-L+1[/latex]
JeremyGuo
简单题解:
通过容斥原理处理出公因数为i的对数然后我们直接根据期望的定义计算即可