Problem
Description
给定三个十进制数 ,求在 进制下,有多少个数值互不相等的纯循环小数可以用分数 表示。
一个数是纯循环的,当且仅当其可以写成以下形式:
其中, 是一个整数,;对于 , 是 进制下的一位数字。
需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成 的循环或是 的循环。
Constraints
Link
Solution
Analysis
对于 ,观察 进制转换的过程,若其为纯循环小数,设其循环节长度为 ,则有:
那么 即为 在模 意义下的逆元,而这是 的充要条件。
那么答案即为:
现在问题转化为求 和 的前缀和。设:
对于 ,由于 ,有:
预处理 即可 回答,时间复杂度 。
对于 ,发现 一项难以处理,考虑将其消掉。
观察到 ,故可以将 卷上 来杜教筛:
时间复杂度 。
Code
1 |
|