#P3031. 理科男

    ID: 2163 传统题 1000ms 512MiB 尝试: 185 已通过: 51 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理同向双指针组合数学双射计数线性代数与代数等价类划分CF2300Poetize2

理科男

理科男

题目描述

吃过草莓刨冰后,Vani 问了 cl 一个关于分数的问题。

给定分数 AB\frac AB 和进制 KK。如果 AB\frac AB 在 KK 进制下是有限小数,求小数点后的最少位数。如果是循环小数,求循环开始前的小数位数和循环节长度,二者都取最短的表示。

输入格式

第一行一个正整数 TT,表示数据组数。接下来 TT 行,每行三个整数 A,B,KA,B,K,以空格分隔。

输出格式

对每组数据输出一行两个整数 M,RM,R,以一个空格分隔。

  • 若为有限小数,MM 是小数点后的位数,R=0R=0。
  • 若为循环小数,MM 是小数点后、循环开始前的位数,RR 是最短循环节的长度。纯循环小数的 M=0M=0。

数据范围

1≤T≤101\le T\le10,1≤A<B≤10121\le A<B\le10^{12},2≤K≤10122\le K\le10^{12}。原赛 50%50\% 的数据满足 B≤100000B\le100000。

样例

3
1 8 10
17 99 10
217 990 10
3 0
0 2
1 2

样例解释

三组数据都是十进制。18=0.125\frac18=0.125,1799=0.17‾\frac{17}{99}=0.\overline{17},217990=0.219‾\frac{217}{990}=0.2\overline{19}。

BZOJ 题面存档