本文主要是介绍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/10为例：1/10 2/10 4/10 8/10 16/10 32/10 64/10....
取模后：1/10 2/10 4/10 8/10 6/10 2/10 4/10
这不就是个循环吗？循环节为4，循环起点为2，正好与题目相符。。如何去找循环节和循环起点？
由于是二进制，所以分子可以表示为2^x,而模数即q
2^x=2^y(mod q)，2^x(2^(y-x)-1)=0(mod q)，即p|2^x(2^(y-x)-1)
因为x^(y-1)-1为奇数，所以p|2^x
首先把q尽量整除2直到不能整除为止，这个步骤的次数就是满足原式最小的x，并得到q'。
2^(y-x)=1(mod q')
根据欧拉定理，t=y-x=phi(q')满足此式。
因为2^phi(q')和q'的最大公约数可能不为1
所以不一定是最小值，需要枚举phi(q')约数。
用int交就WA，用long long就过了
代码如下：
<span style="font-size:18px;">#include <cmath>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;char str[100];
vector<LL> vec;LL gcd(LL a, LL b) {return b ? gcd(b, a%b) : a;
}LL euler_phi(LL n) {LL ans = n;LL m = sqrt(n+0.5);for(LL i=2; i<=m; ++i) {if(n%i == 0) {n /= i;ans = ans/i*(i-1);while(n%i == 0)n /= i;}}if(n > 1)ans = ans/n*(n-1);return ans;
}void get_fac(LL n) {LL m = sqrt(n+0.5);for(LL i=1; i<=m; ++i) {if(n%i == 0) {vec.push_back(i);if(n/i != i)vec.push_back(n/i);}}
}LL pow_mod(LL a, LL b, LL m) {LL ans = 1;while(b) {if(b & 1) {ans = ans*a%m;}a = a*a%m;b >>= 1;}return ans%m;
}int main(void) {char ch;LL cas = 0, tmp, x, y, p, q;while(scanf("%s", str) != EOF) {vec.clear();sscanf(str, "%lld%c%lld", &p, &ch, &q);if(!p) {printf("Case #%lld: 1,1\n", ++cas);continue;}//printf("p = %d\tq = %d\n", p, q);tmp = gcd(p, q);p /= tmp;q /= tmp;x = 1;while(q % 2 == 0) {q >>= 1;++x;}tmp = euler_phi(q);get_fac(tmp);sort(vec.begin(), vec.end());for(int i=0; i<vec.size(); ++i) {if(pow_mod(2, vec[i], q) == 1) {y = vec[i];break;}}printf("Case #%lld: %lld,%lld\n", ++cas, x, y);}return 0;
}</span>这篇关于poj 3358 Period of an Infinite Binary Expansion(数论：欧拉函数+快速幂取模)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
