【poj 3358】Period of an Infinite Binary Expansion(数论同余，欧拉定理）

· · 个人记录

题意

给定p, q，求\frac p q 的二进制循环节开始部分和循环节长度

分析

二进制小数是乘二取整

先将\frac p q 化至最简，此时gcd(p,q) = 1

如果出现循环，也就是

p2^i \equiv p2^j (\mod q)

因为gcd(p,q) = 1 所以逆元存在

2^i = \equiv 2^j + qt

令i >= j 求最小的j和 i-j+1;

2^i - 2^j = 2^j(2^{i-j}-1) = qt

因为2^{i-j}-1不包含因子2，所以qt中的因子2全来自2^j

所以j最小为q中因子2的个数

令 q = q / 2^j

令k = i-j

2^k = 1(\mod q)

求解最小的k

欧拉定理的常见应用

(不会的看poj3696的博客)

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll p,q;

ll get_phi(ll n) {
    ll res = n;
    for(ll i=2;i*i<=n;i++) {
        if(n%i==0) {
            res = res-res/i;
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1) res = res-res/n;
    return res;
}
ll mul(ll a,ll b,ll mod) {
    ll res=0;
    while(b){
        if(b&1) res =(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
ll qpow(ll a,ll b,ll mod) {
    ll res = 1;
    while(b) {
        if(b&1) res = mul(res,a,mod);
        a = mul(a,a,mod);
        b>>=1;
    }
    return res;
}
int main() {
    int ca=0;
    while(scanf("%lld/%lld",&p,&q)!=EOF){
        ll g = __gcd(p,q);
        p/=g;q/=g;
        ll be = 1;
        while(q%2==0) {
            q/=2;
            be++;
        }
        ll n = get_phi(q);
        ll len = n;
        for(ll i=1;i*i<=n;i++) {
            if(n%i==0){
                if(i < len && qpow(2,i,q)==1) len=i;
                if((n/i)<len && qpow(2,n/i,q)==1) len = n/i;    
            }
        }
        printf("Case #%d: %lld,%lld\n",++ca,be,len);
    }
}