1077: 循环节长度
时间限制: 1 Sec 内存限制: 128 MB
提交: 103 解决: 37
[提交][状态][讨论版]
题目描述
数一有很多的有理数，然而有的是有限小数，如1/2=0.5，1/5=0.2，这些都很好写，但是对于无限循环小数，数一就发愁了，怎么写得完啊。于是数一就想让你告诉他这些有理数的循环节长度是多少。
输入
多组数据，每组数据是两个整数p,q(0<=p<10^9,0<q<=10^9)，表示一个有理数的分子与分母。
输出
若为有限小数，则输出0，若为无限循环小数，请输出循环节长度。
样例输入
1 2
1 3
2 10
2 7
5 6
样例输出
0 1 0 6 1
想法：
1 证明有理数a/b可以写成无限循环小数
1) 根据抽屉原理 存在10^m%b=10^n%b
对于任何b存在一个数c (b|c 且c可以写成10^i(10^j-1)的形式 ）
2）a/b=d/c [ d=a*c/b 则d是整数 ]=(d/10^i) * ( 1/(10^j-1) )
3) x= 1/(10^j-1) 一定是有理小数并且循环节长度为j
方法
1 用bsgs 求解（10^j%b=1)
2 用数组实现hash
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=;
struct node {
int k1,k2;
int _next;
};
int hs[mod+];
node hn[mod+]; int cnt;
int gcd (int x,int y) {
return !y?x:gcd(y,x%y);
}
void _add (int x, int key) {
int head=x%mod;
hn[++cnt].k2=key; hn[cnt].k1=x;
hn[cnt]._next=hs[head];
hs[head]=cnt;
}
int _find (int x) {
int head=x%mod;
for (int i=hs[head];i!=-;i=hn[i]._next) {
if (hn[i].k1==x)
return hn[i].k2;
}
return -;
}
int bsgs (int k,int p) {
cnt=; memset (hs,-,sizeof(hs));
LL x=; int t=sqrt(p)+;
for (int i=;i<t;i++) {
_add (x,i);
x=x*k%p;
}
LL y=;
for (int i=;i<=t;i++) {
y=y*x%p; // 不使用long long 会溢出
int ans=_find(y);
if (ans>=) return i*t-ans;
}
}
int main ()
{
int a,b;
while ( ~scanf ("%d %d",&a,&b) ) {
int k=gcd (a,b); a/=k; b/=k;
while (b%==) b/=;
while (b%==) b/=;
if (b==) printf("0\n");
else printf("%d\n",bsgs(,b) );
}
return ;
}