首页 > 代码库 > BZOJ2480: Spoj3105 Mod
BZOJ2480: Spoj3105 Mod
已知数a,p,b,求满足a^x≡b(mod p)的最小自然数x。p不一定是素数。
先附上AekdyCoin大牛的题解:http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4
然后我们来证明算法的正确性。
不妨认为我们消因子后,a->a,b->b‘,c->c‘,d,e(指文中的D),除去的gcd之积为f,且(a,c‘)=1
那么其实 a^d=f*e,然后我们用BSGS求解 e*a^x=b‘ mod c‘ 因为(a,c‘)=1
而且x就是(a^inf,c)
然后假设我们得到了一个解 e*a^x=b‘ mod c‘ 考虑回推出原同余方程的解。
由裴蜀定理值存在唯一的 e*a^x+c‘*y=b‘ (注意现在是等号,而不是模意义)
我们在等式两边乘以f,就得到了 a^d*a^x+c*y=b ,也就是a^(d+x)=b mod c,这说明x+d是原方程的解。
我知道公式写成这样是没人耐心看的
还是看代码比较亲切
map<int,int>mp;inline int gcd(int x,int y){return y?gcd(y,x%y):x;}inline int power(int x,int y,int p){ int t=1; for(;y;y>>=1,x=(ll)x*x%p) if(y&1)t=(ll)t*x%p; return t;}inline int solve(int a,int b,int c){ a%=c;b%=c; for(int i=0,j=1;i<=50;i++,j=(ll)j*a%c)if(j==b)return i; int d=0,e=1%c,t; while((t=gcd(a,c))!=1) { if(b%t)return -1; c/=t;b/=t;d++;e=(ll)e*a/t%c; } mp.clear(); int m=ceil(sqrt(c)); for(int i=0,j=1;i<m;i++,j=(ll)j*a%c)mp[(ll)b*j%c]=i; a=power(a,m,c); for(int i=0,j=e;i<=m;i++,j=(ll)j*a%c) if(i&&mp.find(j)!=mp.end()) return i*m-mp[j]+d; return -1;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); while(1) { int a=read(),c=read(),b=read(),t; if(!(a||b||c))break; if((t=solve(a,b,c))>=0)printf("%d\n",t); else printf("No Solution\n"); } return 0;}
BZOJ2480: Spoj3105 Mod
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。