首页 > 代码库 > poj3708：函数式化简+高精度进制转换+同余方程组
poj3708：函数式化简+高精度进制转换+同余方程组
题目大意
给定一个函数
找出满足条件
等于 k
的最小的x
m,k,d已知 其中 m，k 很大需要使用高精度存储
思路：
对 函数f(m)进行化简 ，令t=ceil( log(d,m) )
可以得到 f(m)=d ^ t * ( a [ m / (d^t) ] ) + d ^ (t-1) * ( b[ m/( d^(t-1) ) ] )......+b [m%d] ；
我们一看，每一项都是 跟 d 的次方有关，所以考虑使用 d 进制进行计算
设 m=a1b1b2b3b4（d进制）
那么 f(m)=a[a1]b[b2]b[b3]b[b4]（d进制）
以此类推
fx（m）=k，即 m通过 x次上述变换后得到了k （这里的 m 和 k 均为 d 进制）
于是 我们可以找到 m 每一位第一次等于k的情况以及这一位的循环节 分别存在数组中
那么问题就转化为了解同余方程
这个题还有很多无解的情况，需要注意特判
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 100000char m[110];char k[110];long long p[110];long long q[110];long long start[1000];long long ans[1000];long long res[1000];long long mm[1000];long long kk[1000];long long a[1000];long long b[1000];long long d;long long vi[110];long long getnum(char c){ return c-‘0‘;}void trans(char* str,long long base0,long long base1){ memset(res,0,sizeof(res)); long long y,i,j; start[0]=strlen(str); for(i=1;i<=start[0];i++) { start[i]=getnum(str[i-1]); } while(start[0]>=1) { y=0; //余数 ans[0]=start[0]; for(i=1;i<=start[0];i++) { y=y*base0+start[i]; ans[i]=y/base1; y%=base1; } res[++res[0]]=y; //这一轮的余数 i=1; while(i<=ans[0]&&ans[i]==0) i++; memset(start,0,sizeof(start)); for(j=i;j<=ans[0];j++) start[++start[0]]=ans[j]; memset(ans,0,sizeof(ans)); } return;}long long save(long long *dis){ for(long long i=res[0];i;i--) { dis[res[0]-i]=res[i]; } return res[0];}long long exgcd(long long a,long long b,long long &x,long long &y){ if(!b) { x=1; y=0; return a; } long long tt=exgcd(b,a%b,x,y); long long t; t=x; x=y; y=(t-a/b*y); return tt;}long long solve(long long r){ long long a1,a2,b1,b2,x,y,A,B,C,d,t; a1=a[0]; b1=b[0]; for(long long i=1;i<r;i++) { a2=a[i]; b2=b[i]; A=a1; B=a2; C=b2-b1; d=exgcd(A,B,x,y); if(C%d) { return -1; } t=B/d; x=(x*(C/d)%t+t)%t; b1=a1*x+b1; a1=a1/d*a2; } return b1;}int main(){ while(scanf("%lld",&d),d!=-1) { for(long long i=1;i<d;i++) scanf("%lld",p+i); for(long long i=0;i<d;i++) scanf("%lld",q+i); scanf("%s%s",m,k); trans(m,10,d); long long nm=save(mm); trans(k,10,d); long long nk=save(kk); if(nm!=nk) { puts("NO"); continue; } memset(a,-1,sizeof(a)); memset(b,-1,sizeof(b)); bool have=1; for(long long i=0;i<nm;i++) { bool ok=0; long long tmp=0; memset(vi,0,sizeof(vi)); for(long long j=mm[i];;) { if(j==kk[i]) { if(ok==0) { b[i]=tmp; ok=1; } else { a[i]=tmp-b[i]; break; } } tmp++; if(i==0) j=p[j]; else j=q[j]; if(tmp>=5000) { ok=0; break; } } if(!ok) { have=0; break; } } if(!have) { puts("NO"); continue; } long long ans=solve(nm); if(ans==-1) { puts("NO"); continue; } printf("%lld\n",ans); } return 0;}
poj3708：函数式化简+高精度进制转换+同余方程组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。