P1587 [NOI2016]循环之美

    • 413通过
    • 1.2K提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 数论,数学 NOI系列 2016 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 $k$ 进制下,一个数的小数部分是纯循环的,那么它就是美的。现在,牛牛想知道:对于已知的十进制数 $n$ 和 $m$,在 $k$ 进制下,有多少个数值上互不相等的纯循环小数,可以用分数 $\frac xy$ 表示,其中 $1≤x≤n,1≤y≤m$,且 $x,y$是整数。一个数是纯循环的,当且仅当其可以写成以下形式:

    $a.\dot{c_1} c_2 c_3 \dots c_{p - 1} \dot{c_p}$

    其中,$a$ 是一个整数,$p≥1$;对于 $1≤i≤p$,$c_i$ 是 $k$ 进制下的一位数字。

    例如,在十进制下,$0.45454545……=0.\dot {4} \dot {5}$是纯循环的,它可以用 $\frac {5}{11}$、$\frac{10}{22}$ 等分数表示;在十进制下,$0.1666666……=0.1\dot6$则不是纯循环的,它可以用 $1/6$ 等分数表示。需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环;而一个小数部分非 $0$ 的有限小数不是纯循环的。

    输入输出格式

    输入格式:

    只有一行,包含三个十进制数N,M,K意义如题所述,保证 1≤n≤10^9,1≤m≤10^9,2≤k≤2000

    输出格式:

    一行一个整数,表示满足条件的美的数的个数。

    输入输出样例

    输入样例#1: 复制
    2 6 10
    输出样例#1: 复制
    4

    说明

    满足条件的数分别是:

    1/1=1.0000……
    1/3=0.3333……
    2/1=2.0000……
    2/3=0.6666……

    1/1 和 2/2 虽然都是纯循环小数,但因为它们相等,因此只计数一次;同样,1/3 和 2/6 也只计数一次。

    这部分将提供一个将分数化为对应的小数的方法,如果你已经熟悉这个方法,你不必阅读本提示。

    分数可以通过除法,用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起,设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 a位和小数点后第 b 位(特殊地:如果其中一个对应的商数位是个位,则认为 a=0;不妨设 a<b),则其循环部分可以用小数点后第 a+1位到小数点后第 b位的循环来表示。

    例如:在十进制下,将 511转化为小数时,个位开始的商数依次为 4,5,4,…,对应的余数分别为 6,5,6,…。余数第一次重复出现的位置是个位和小数点后第 2 位,那么 a=0,b=2

    a=0,b=2即其循环部分可以用小数点第 1位到第 3位来表示。表示为:511=0.45454545…=0.4˙5˙。

    在十进制下,将 16 转化为小数时,个位开始的商数依次为 1,6,6,…,对应的余数分别为 4,4,4,…。余数第一次重复出现的位置是小数点后第 1 位和小数点后第 2 位,即其循环部分可以用小数点后第 2 位来表示。表示为:16=0.1666……=0.16˙。

    需要注意的是:商数重复出现并不代表进入了循环节。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。