跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0167. #2085. 「NOI2016」循环之美

  • ID: 173
  • 传统题
  • 2000ms
  • 512MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2085. 「NOI2016」循环之美

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 进制下,一个数的小数部分是纯循环的,那么它就是美的。

现在,牛牛想知道:对于已知的十进制数 和 ,在 进制下,有多少个数值上互不相等的纯循环小数,可以用分数 表示,其中 ,且 是整数。

一个数是纯循环的,当且仅当其可以写成以下形式:

其中, 是一个整数,;对于 , 是 进制下的一位数字。

例如,在十进制下,0.45454545⋯=0.˙4˙5 是纯循环的,它可以用 、 等分数表示;在十进制下,0.1666666⋯=0.1˙6 则不是纯循环的,它可以用 等分数表示。

需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成 的循环或是 的循环;而一个小数部分非 的有限小数不是纯循环的。

输入格式

输入文件只有一行,包含三个十进制数 ,意义如题所述。

输出格式

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

样例

样例输入 1

2 6 10

样例输出 1

4

样例解释 1

满足条件的数分别是:

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

样例输入 2

23333 666666 310

样例输出 2

5089564081

数据范围与提示

对于所有的测试点,保证 ,,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 50 题。保留原作者与原赛事署名。