97 lines
2.0 KiB
C
97 lines
2.0 KiB
C
#include <stdio.h>
|
||
|
||
typedef unsigned long long int ul;
|
||
|
||
|
||
ul gcd(ul a, ul b)
|
||
{
|
||
if (!b) return a;
|
||
return gcd(b, a % b);
|
||
}
|
||
|
||
|
||
char recurring_decimal_digit(ul a, ul b, ul n)
|
||
{
|
||
ul d = gcd(a, b);
|
||
a /= d;
|
||
b /= d;
|
||
|
||
/* 将
|
||
* \frac{a}{b}
|
||
* 转化为
|
||
* \frac{a}{2^{b2} \cdot 5^{b5} \cdot b'}
|
||
* 的形式
|
||
*/
|
||
ul b2 = 0;
|
||
ul b5 = 0;
|
||
for (; !(b % 2); b /= 2) b2 += 1;
|
||
for (; !(b % 5); b /= 5) b5 += 1;
|
||
|
||
/* 计算
|
||
* \frac{1}{10^\mbox{offset}} \cdot \frac{a \cdot m}{b}
|
||
* 其中
|
||
* \mbox{offset} = \max(c2, c5)
|
||
* m = \frac{10^\mbox{offset}}{2^{b2} \cdot 5^{b5}}
|
||
*
|
||
* offset 表示原小数中前 offset 位不在循环体内
|
||
*/
|
||
ul m = 1;
|
||
ul base = 2;
|
||
ul offset = b5;
|
||
ul exp = b5 - b2;
|
||
if (b2 > b5) {
|
||
base = 5;
|
||
offset = b2;
|
||
exp = b2 - b5;
|
||
}
|
||
while (exp--) m *= base;
|
||
|
||
/*
|
||
* 计算
|
||
* \frac{1}{10^\mbox{offset}} \cdot \left( \mbox{pre} + \frac{r_m \cdot r_a \mod b}{b} \right)
|
||
* 其中
|
||
* \frac{r_m \cdot r_a \mod b}{b}
|
||
* 为纯循环小数，容易计算循环节
|
||
*/
|
||
ul qm = m / b;
|
||
ul rm = m % b;
|
||
ul qa = a / b;
|
||
ul ra = a % b;
|
||
ul pre = (qa * b + ra) * qm + qa * rm;
|
||
|
||
/* 若 n 在非循环节中，则直接返回 pre 中对应的数位 */
|
||
if (n <= offset) {
|
||
n = offset - n;
|
||
while (n--) pre /= 10;
|
||
return pre % 10;
|
||
}
|
||
|
||
n -= offset;
|
||
a = rm * ra % b;
|
||
if (!a) return 0; // 有限小数补0
|
||
|
||
/* 计算循环节unit，进而将 n 轮运算优化为 n % unit 轮 */
|
||
ul unit = 1;
|
||
ul mod = 10;
|
||
for (; 1 != mod; mod = (10 * mod) % b) unit += 1;
|
||
|
||
ul r = 0;
|
||
n %= unit;
|
||
if (!n) n = unit;
|
||
while (n--) {
|
||
a *= 10;
|
||
r = a / b;
|
||
a -= r * b;
|
||
}
|
||
|
||
return r % 10;
|
||
}
|
||
|
||
|
||
int main(int argc, char **argv)
|
||
{
|
||
if (3 > argc) return -1;
|
||
printf("%d\n", recurring_decimal_digit(atoi(argv[1]), atoi(argv[2]), atoi(argv[3])));
|
||
return 0;
|
||
}
|