ural 1468 Fraction

本文从WordPress迁移而来, 查看全部WordPress迁移文章

数学 模拟

题意:a/b,用k进制表示,如果是循环小数用括号括起循环节

这题选拔赛又没做出来,连循环节都搞出来但是忘记了怎么把小数部分换成k进制。

先处理整数部分:整数部分应该比较简单的,求出a/b的十进制数,然后不断/k取余,然后逆过来输出就是整数部分

小数部分:取a%b,因为之前已经计算了整数部分,剩下a%b进行小数部分的处理。关于换成k进制的做法是这样的

n/b换成k进制(其中n < b )

1
2
3
4
5
1.  s1 = n * k / b    ......第一个小数的结果
nn = n * k % b ......余下来的余数
2. s2 = nn * k / b ......第二个小数的结果
nnn = nn * k % b ......余下的余数
..............................

以此类推,直到n为0为止,也就是余数变为0为止

何时出现循环小数?如果这次计算后,得到一个余数m,发现这个余数m之前已经出现过了,那么从m第1次出现到现在这个位置,就是一个循环节

所以,但能除净的时候,不能出现余数相同的情况;如果一旦出现了余数相同(即某个余数第2次出现的时候),就应该停止了,已经找到了循环节了

另外可知整个除法的过程,最多除b次,因为余数一定是[0,b-1]以内的数,就算不重复出现,也只会产生b个不同的余数,这就是所谓的鸽巢原理(抽屉原理)嘛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 10010
#define cl memset
#define pb push_back

int a,b,k;
vector<int>vec,_vec;
int first[N],pos;

void _inter(int n){
vec.clear();
if(n == 0){
vec.pb(0); return ;
}
while(n){
vec.pb(n % k); n /= k;
}
}

void _double(int n){
pos = -1; _vec.clear();
cl(first,-1,sizeof(first));
first[n] = 0;
while(n){
_vec.pb(n * k / b);
n = n * k % b;
if(first[n] != -1){
pos = first[n]; break;
}
first[n] = _vec.size();
}
}

int main(){
while(scanf("%d%d",&a,&b)!=EOF){
if(a == 0 && b == 0) break;
scanf("%d",&k);
_inter(a/b);
for(int i = vec.size() - 1; i >= 0; i--)
printf("%c",vec[i]<=9 ? '0'+vec[i] : 'A'+vec[i]-10);
if(a % b == 0){
puts(""); continue;
}
_double(a%b);
putchar('.');
for(int i = 0; i < _vec.size(); i++){
if(i == pos) putchar('(');
printf("%c",_vec[i]<=9 ? '0'+_vec[i] : 'A'+_vec[i]-10);
}
if(pos != -1) putchar(')');
puts("");
}
return 0;
}