题目链接：
?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;}
做事不怕难，自无难人事。
