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; imes;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; imes;frac{1}{P'} floor$,
$b_i=10; imes;b_{i-1};mod;P',a_i=lfloor10; imes;frac{b_i}{P'} floor$.
当找到最小的$p,q(p<q)$满足$b_p=b_q$时,答案为$q-p$.
因为$(P',10)=1$,所以$(P',b_i)=1$.
设$10x;equiv;1(mod;P')$,若$p ot=1$,则$b_{p-1}=x; imes;b_p;mod;P'=x; imes;b_q;mod;P'=b_{q-1}$.
出现了更早的重复$b_{p-1}=b_{q-1}$,所以最早的重复在$p=1$,所以$frac{1}{P'}$为纯循环小数.
设$y$为最小的满足$b_y=b_1; imes;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 45000 using 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 ",x,max(cnt,tot)); } } int main(){ freopen("pro.in","r",stdin); freopen("pro.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }