poj2462PeriodofanInfiniteBinaryExpansion

欧拉定理。根据分数转换成2进制的过程，分子每次都乘2。对于循环节x，当2^x = 1(mod b)时肯定是循环节。显然当分母不能整除2的时候，即分母和2互质的话，就可以利用欧拉定理，使得2^(Euler(b)) = 1(mod b)。然后对于Euler(b)，枚举其因子，找到最小循环节就可以了。

#include algorithm
#include iostream
#include cstring
#include cstdio
#include vector
#include cmath
#include set
#include map
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
#define REP(i, n) for(int i = 0; i i ++)
using namespace std;
const int N = 400100;
bool isp[N];
vector int
vector LL hav;
void get_P()
{
CLR(isp, true);p.clear();
for(int i = 2; i i ++)
{
if(isp[i])
{
p.push_back(i);
if(i 1111) for(int j = i * i; j j += i)
{
isp[j] = false;
}
}
}
LL Euler_phi(LL n)
{
LL ret = n;
for(int i = 0; (LL)p[i] * p[i] i ++) if(n % (LL)p[i] == 0)
{
ret = ret / p[i] * (p[i] - 1);
while(n % p[i] == 0) n /= p[i];
}
if(n 1) ret = ret / n * (n - 1);
return ret;
LL Mul(LL a, LL b, LL mod)
{
LL ret = 0;
while(b)
{
if(b 1)
ret = (ret + a) % mod;
a = a * 2 % mod;
b = 1;
}
return ret;
LL Pow(LL a, LL b, LL mod)
{
LL ret = 1;
while(b)
{
if(b 1) ret = Mul(ret, a, mod);
a = Mul(a, a, mod);
b = 1;
}
return ret;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
void get_hav(LL n)
{
hav.clear();
for(int i = 0; i p.size() n i ++)
{
while(n % (LL)p[i] == 0)
{
n /= p[i];
hav.push_back(p[i]);
}
}
if(n 1) hav.push_back(n);
int main()
{
int cas = 1;
LL ans, m, x, a, b, g;get_P();
while(scanf("%I64d/%I64d", a, b) != EOF)
{
g = gcd(a, b);
a /= g;b /= g;ans = 1;
while(b % 2 == 0)
{
ans ++;
b /= 2;
a %= b;
g = gcd(a, b);
a /= g;b /= g;
}
x = Euler_phi(b);
get_hav(x);
for(int i = 0; i hav.size(); i ++)
{
if(Pow(2LL, x / hav[i], b) == 1)
x /= hav[i];
}
printf("Case #%d: %I64d,%I64d\n", cas ++, ans, x);
}