首页 > 代码库 > [bzoj 3031] 理科男
[bzoj 3031] 理科男
给定一个进制分数
求是否是循环小数，且求出循环节长度
暴力
il int find(int p){ int head=last[p%mod]; while(head&&pr[head].p!=p)head=pr[head].next; if(!head)head=++siz; return head;}int main(){ T=gi; while(T--){siz=0;memset(last,0,sizeof(last)); ll p,q,k; p=gi;q=gi;k=gi; ll d=gcd(p,q); p/=d;q/=d; p%=q; for(int i=1;;i++){ p*=k; if(!(p%q)){ printf("%d 0\n",i); break; } int t=find(p); if(!pr[t].id)pr[t]=(data){i,p}; else{ printf("%d %d\n",pr[t].id-1,i-pr[t].id); break; } p%=q; } } return 0;}
正解：
首先设一个序列
,
表示原数小数点后i位，那么
然后余数
且
上面暴力是计算到这样一对的时候停止
那么考虑a的性质 如果 ，那么
设
如果 那么
就是出现了更早的重复，所以最早的重复肯定是在p=1，说明这样形式的只有纯循环小数
如果满足
于是
然后就是求一个K模B的阶的问题。
阶很好求。。
#include<queue>#include<map>#include<cstdio>#include<string.h>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;typedef pair<int,int>Pii;const int inf=0x7fffffff;const ll infll=(1ll<<60);#define dbg(n) cerr<<#n"="<<n<<endl;#define Ri register int#define gc getchar()#define il inlineil ll read(){ bool f=true; register ll x=0;char ch; while(!isdigit(ch=gc)) if(ch==‘-‘)f=false; while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-‘0‘; ch=gc; } return f?x:-x;}#define X first#define Y second#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}map<ll,int> Calc(ll x){ map<ll,int> prime; for(int i=2;(ll)i*i<=x;i++) if(x%i==0){ int sum=0; while(x%i==0)x/=i,sum++; prime[i]=sum; } if(x>1)prime[x]=1; return prime;}il ll Euler_phi(ll x,const map<ll,int>& prime){ ll ans=x; for(map<ll,int>::const_iterator i=prime.begin();i!=prime.end();i++) if(i->Y)ans=ans/i->X*(i->X-1); return ans;}il ll Mul(ll a,ll b,ll mod){ ll ans=0,p=a%mod; while(b){ if(b&1)ans=(ans+p)%mod; p=(p+p)%mod; b>>=1; } return ans;}il ll Mod(ll a,ll b,ll mod){ ll ans=1,p=a%mod; while(b){ if(b&1)ans=Mul(ans,p,mod); p=Mul(p,p,mod); b>>=1; } return ans;}ll A,B,K;int main(){ int T; cin>>T; while(T--){ A=gi;B=gi;K=gi; ll d=gcd(A,B); A/=d;B/=d; map<ll,int> prime_B=Calc(B),prime_K=Calc(K); int M=0;ll tmpB=B; for(map<ll,int>::const_iterator i=prime_K.begin();i!=prime_K.end();i++){ int p=prime_B[i->X];prime_B[i->X]=0; M=max(M,(p+i->Y-1)/i->Y); while(p) tmpB/=i->X,p--; } ll R=0; if(tmpB!=1){ ll phi_B=Euler_phi(tmpB,prime_B); R=phi_B; prime_B=Calc(R); for(map<ll,int>::const_iterator i=prime_B.begin();i!=prime_B.end();i++){ int p=i->Y; while(p){ if(Mod(K,R/i->X,tmpB)==1) p--,R/=i->X; else break; } } } cout<<M<<" "<<R<<endl; } return 0;}
[bzoj 3031] 理科男
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。