题目链接：
http://poj.org/problem?id=3358
题目大意：
输入一个有理数，形式为分数形式p/q，令{x}为该有理数二进制形式的小数部分，且{x}具有循环
性，{x} = 0.A1A2A3…Ar(Ar+1Ar+2…Ar+s)^w。循环从r+1位开始，循环节为s。
现在称x1 = A1A2A3…Ar为{x}的循环前缀，x2 = Ar+1Ar+2…Ar+s为{x}的循环部分。
现在让循环前缀的长度和循环部分的长度尽可能小。求最小循环部分的起始位置以及最小
的循环长度。
例如：1/10 = 0.0001100110011(00110011)^w，0001100110011是1/10的一个循环前缀，
00110011是1/10的一个循环部分。但是都不是最小的。因为1/10 = 0.0(0011)^w，0是1/10的
最小循环前缀，0011是1/10的最小循环部分。答案为：1/10的最小循环部分从第2位开始，最小
循环长度为4。
思路：
小数转换为二进制是每次乘以2，减去大于1的整数部分(没有则不减，继续乘以2)，只留小数部分。
现在观察1/10这组数据。小数表示太过繁琐，这里用分数来实现二进制的转换，来观察规律。
将1/10按照乘二法可得：
1/10 2/10 4/10 8/10 16/10 32/10 …
然后每个分子尽可能减去10，得到：
1/10 2/10 4/10 8/10 6/10 2/10 …
发现从第2位开始出现了重复，而重复的循环节为4，其实就是最小循环长度。
由于是二进制，可知1*2^2 = 1*2^5(mod 10)。
现在考虑p/q。设p1 = p/gcd(p，q)，q1 = q/gcd(p，q)。 由于是二进制，p1*2^i ≡ p1*2^j(mod q1)。
经变换可得：p1 * 2^i * (2^(j-i) - 1) ≡ 0(mod q1)。
因为p1和q1互质，所以2^i * (2^(j-i) - 1) % q1 = 0。2^(j-i) - 1为奇数，2^i为偶数，2^i全部来源于q1，
q1中有多少个2的幂，i就是多少，也是循环开始位置的前一位。
将q1中2^i化简去后，得到：(2^(j-i) - 1) % q1 = 0。令x = j-i，就是求2^x ≡ 1(mod q1)中的x最小为多少
因为q1与2互质(已经消去2了)，所以一定有解。根据欧拉定理2^φ(q1) ≡ 1(mod q1)。但是φ(q1)不一定是
最小的值，但是肯定是φ(q1)的约数。枚举φ(q1)的约数，找到最小的值。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int GCD(int a,int b)
{
if(b == 0)
return a;
return GCD(b,a%b);
}
int MultiPower(int a,int b,int m) //a^b % m
{
int ans = 1;
while(b > 0)
{
if(b&1)
ans = (__int64)ans * a % m; //ans = ans * a % m 结果会溢出。
a = (__int64)a * a % m;
b >>= 1;
}
return ans;
}
int Euler(int n) //求欧拉函数φ(q1)
{
int ret = n;
for(int i = 2; i*i <= n; ++i)
{
if(n%i == 0)
{
n /= i;
ret = ret - ret/i;
}
while(n % i == 0)
n /= i;
}
if(n > 1)
ret = ret - ret/n;
return ret;
}
int factor[1010000];
int main()
{
int kase = 0,p,q;
while(~scanf("%d/%d",&p,&q))
{
int gcd = GCD(p,q);
p /= gcd;
q /= gcd;
int time = 1;
while(q%2 == 0)
{
q >>= 1;
time++;
}
int phi = Euler(q);
int ans = 0;
if(phi == 1)
ans = 1;
else
{
int id = 0;
for(int i = 1; i*i <= phi; ++i) //分解φ(q1)
{
if(phi % i == 0)
{
factor[id++] = i;
factor[id++] = phi/i;
}
}
sort(factor,factor+id);
for(int i = 0; i < id; ++i) //找到最小的值
{
if(MultiPower(2,factor[i],q) == 1)
{
ans = factor[i];
break;
}
}
}
printf("Case #%d: %d,%d\n",++kase,time,ans);
}
return 0;
}
POJ3358 Period of an Infinite Binary Expansion【欧拉函数】
原文：http://blog.csdn.net/lianai911/article/details/44597239