本文主要是介绍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);
然后 p'*2^i = p'*2^j (mod q') (i<j)
经过变换得到：
p'*2^i*(2^(j-i)-1) ==0 (mod q')
也就是 q' | p'*2^i*(2^(j-i)-1)
由于gcd(p',q')=1,
得到： q' | 2^i*(2^(j-i)-1)
因为2^(j-i)-1为奇数，所以q'有多少个2的幂，i就是多少，而且i就是循环开始位置的前一位。
q''为q'除去2的幂之后的数
2^x ==1 (mod q'') , q''和2互质,可以利用欧拉定理求解
这篇关于POJ 3358 Period of an Infinite Binary Expansion(数论，欧拉定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
