Period of an Infinite Binary Expansion 题解

Solution

简单写一下思考过程，比较水的数论题

第一个答案几乎已经是可以背下来的，在此不再赘述

考虑我们已经知道了\((p,q)\)，其中\((p \perp q) \wedge (q \perp 2)\)，要求的是循环长度

首先看看样例的\(\frac{1}{5}\)怎么做呢

观察答案，可以得到$$\frac{1}{5}=\sum_{t>0}(\frac{3}{16^t})$$

简单思考一下，发现答案和\(p\)没关系，和\(q\)的关系为

\[\frac{1}{q}=\sum_{t>0}{\frac{s}{2^{kt}}}
\]

其中\(s,t \in \text{N}^\ast\)

简单化下式子，等比数列求和得$$2^k-1=qS$$

即$$2^k \equiv 1 \pmod{q}$$

所以\(k|\varphi(q)\)

秒杀！

Code

#include <cstdio>

#include <iostream>

typedef long long LL;

using namespace std;

inline LL gcd(LL x, LL y) {return (y == 0) ? x : gcd(y, x % y);}

LL p, q, ans1, ans2, d, n, i, id, phi;

inline long long mul(long long a,long long b,long long c){

	long long res = (a*b-(long long)((long double)a/c*b)*c)%c;

	return res < 0 ? res+c : res;

}

inline LL fpow(LL pnt) {

	LL res = 1, base = 2;

	for(; pnt; pnt >>= 1, base = mul(base, base, q))

		if(pnt & 1) res = mul(res, base, q);

	return res;

}

inline void getphi(LL x) {

	phi = x;

	for(i = 2; i * i <= x; ++i) {

		if(!(x % i)) {

			phi = phi / i * (i - 1);

			while(!(x % i)) x /= i;

		}

	}

	if(x ^ 1) phi = phi / x * (x - 1);

}

int main() {

	while(~scanf("%lld/%lld",&p,&q)) {

		++id;

		d = gcd(p, q);

		p /= d, q /= d;

		ans1 = 1; while(!(q & 1)) ++ans1, q >>= 1;

		if(q == 1) ans2 = 0;

		else {

			getphi(q);

			ans2 = 0x7f7f7f7f;

			for(i = 1; i * i <= phi; ++i)

				if(!(phi % i)) {

					if(fpow(i) == 1) {ans2 = i; break;}

					if(fpow(phi / i) == 1) ans2 = phi / i;

				}

		}

		printf("Case #%lld: %lld,%lld\n",id,ans1,ans2);

	}

	return 0;

}

Period of an Infinite Binary Expansion 题解的相关教程结束。