Problem
Description
定义 。
给定 ,求 。
Constraints
保证 为质数且 。
Link
Solution
Analysis
首先容易发现 的递推式为 ,边界条件为 。
则这是一个广义斐波那契数列。
又因 (其中 为递推系数),则有 。
现在已经有了转化 的方法,但是题目要求的是 ,于是考虑转化。
对每个质因子的次数进行 min-max 容斥可得:
构造数列 使得其满足 亦即 ,那么就有:
记 ,考虑 的指数,有:
故:
对于 ,根据其定义式移项可得:
直接按定义式求就可以了。
时间复杂度 。
Code
1 |
|