3358专题

poj 3358 Period of an Infinite Binary Expansion(数论:欧拉函数+快速幂取模)

不太好理解题意的一道题 给出一个除式 要求找到对应二进制的循环起点和最小循环节长度 这里还考察了分数化小数的知识点。。。 这点不会难怪看题解都觉得很吃力 1/10 分数化小数的规律如下: 0.1 0.2 0.4 0.8 1.6 1.2 0.4(每次取左侧一位×2,如果大于10,小数位取1,再把这一位%10) 0    0    0   0    1    1    0 以1/1

POJ 3358 Period of an Infinite Binary Expansion(数论,欧拉定理)

题目:LINK 对于10进制小数转化为2进制小数,我们采用乘2取整法。 对于1/10,  1/10, 2/10, 4/10, 8/10, 16/10, 32/10, 64/10 p对10取余    1/10, 2/10, 4/10, 8/10, 6/10, 2/10, 4/10  发现循环节,且循环节就是题目要求的循环节. 对p/q 首先p'=p/gcd(p,q) q'=q/gcd(p,q);