首页 > 代码库 > [日常训练]yayamao的神题

[日常训练]yayamao的神题

Description

$yayamao$是数学神犇,一天他在纸上计算起了$1/P$, 我们知道按照模拟除法可以得到准确解,例如$1/7=0.(142857),1/10=0.1(0)$。$yayamao$发现无论他如何模拟小数都会出现循环,现在$yayamao$想知道循环的长度以及循环出现之前,小数点后面的未循环的数字的位数。例如$1/15=0.0(6)$,那么它的循环长度为$1$,小数点后面的未循环的数字的位数为$1$;$1/4=0.25(0)$,那么它的循环长度为$1$,小数点后面的未循环的数字的位数为$2$。

Input

数据的第一行是一个整数$T$, 表示数据组数。

接下来$T$组数据,每组数据的第一行是一个正整数$P$。

Output

对于每组数据输出$2$个整数$A,B$, 分别表示循环长度以及小数点后面的未循环的数字的位数。

Sample Input

3

1

2

4

Sample Output

1 0

1 1

1 2

HINT

$1\;\leq\;T\;\leq\;10000,1\;\leq\;P\;\leq\;2\;\times\;10^9$.

Solution

小学奥数中,一个分数如果是纯循环小数,则它的分母是$k=999...9$的因数($k$为最小的这种形式的原分母的倍数),循环节为$k$的位数;

若是混循环小数,则它的分母是$k=999...9000...0$的因数($k$为最小的这种形式的原分母的倍数),循环节为$k$中$9$的个数,小数点后不循环部分的位数为$k$中$0$的个数.

由此可见,设$P=2^{a_1}5^{a_2}P‘((P‘,10)=1)$,则循环部分的位数为$max(a_1,a_2)$.

现在求循环节长度.

设$a_i$表示$P‘$小数点后$i$位上的数,$b_i$表示处理第$i-1$位后的余数.

显然,$b_1=1,a_1=\lfloor10\;\times\;\frac{1}{P‘}\rfloor$,

$b_i=10\;\times\;b_{i-1}\;mod\;P‘,a_i=\lfloor10\;\times\;\frac{b_i}{P‘}\rfloor$.

当找到最小的$p,q(p<q)$满足$b_p=b_q$时,答案为$q-p$.

因为$(P‘,10)=1$,所以$(P‘,b_i)=1$.

设$10x\;\equiv\;1(mod\;P‘)$,若$p\not=1$,则$b_{p-1}=x\;\times\;b_p\;mod\;P‘=x\;\times\;b_q\;mod\;P‘=b_{q-1}$.

出现了更早的重复$b_{p-1}=b_{q-1}$,所以最早的重复在$p=1$,所以$\frac{1}{P‘}$为纯循环小数.

设$y$为最小的满足$b_y=b_1\;\times\;10^{y-1}\;mod\;P‘=b_1$的正整数,则$10^{y-1}\;\equiv\;1(mod\;P‘)$.

问题转化成了求$10$模$P‘$的阶.

因为$(10,P‘)=1$,所以$10^{\phi(P‘)}\;\equiv\;1(mod\;P‘)$.

枚举$\phi(P‘)$的质因数找最小质因数解即可.

#include<cmath>#include<ctime>#include<queue>#include<stack>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 45000using namespace std;typedef long long ll;ll m[N];int f[N],p[N],k,n,x,t,cnt,tot;bool b[N];inline void prime(){    f[1]=1;    for(int i=2;i<N;++i){        if(!b[i]){            p[++n]=i;f[i]=i-1;        }        for(int j=1;j<=n&&i*p[j]<N;++j){            b[i*p[j]]=true;            if(!(i%p[j])){                f[i*p[j]]=p[j]*f[i];                break;            }            f[i*p[j]]=(p[j]-1)*f[i];        }    }}inline int phi(int k){    if(k<N) return f[k];    for(int i=1,j;i<=n;++i)        if(!(k%p[i])){            j=k/p[i];            if(!(j%p[i]))                return p[i]*phi(j);            return (p[i]-1)*phi(j);        }    return k-1;}inline ll mul(int x){    if(x<N) return m[x];    return mul(x>>1)*mul(x+1>>1)%(ll)(k);}inline void Aireen(){    scanf("%d",&t);    prime();m[0]=1ll;    while(t--){        scanf("%d",&k);        cnt=tot=0;        while(!(k%2)){            k>>=1;++cnt;        }        while(!(k%5)){            k/=5;++tot;        }        x=phi(k);        for(int i=1;i<N;++i)            m[i]=m[i-1]*10ll%(ll)(k);        for(int i=sqrt(x);i;--i)            if(!(x%i)){                if(mul(i)==1ll) x=min(x,i);                if(mul(x/i)==1ll) x=min(x,x/i);            }        printf("%d %d\n",x,max(cnt,tot));    }}int main(){    freopen("pro.in","r",stdin);    freopen("pro.out","w",stdout);    Aireen();    fclose(stdin);    fclose(stdout);    return 0;}

[日常训练]yayamao的神题