N次剩余(详解+例题+代码)

2019-04-14 20:24发布

站内文章 / 模拟电子
17943 0 1109
从《国际大学生程序设计大赛算法与实现》中所学
任务：
给定N, a, p, 求出(x^N)%p=a 在模p意义下的所有解x。
说明：
令g为p的原根，因为p为素数，所以phi(p)=p-1。
由原根的性质得：
如果g为p的原根，则：g^i mod p != g^j mod p (p为素数), 其中i != j且i, j介於1至(p-1)之间
所以，可以设g^y=x, g^t=a，则有：
g^(y*N)%p=g^t
又由原根的性质：
g^(y*N)%p=g^t -> (y*N)%(p-1)=t (此方程可以由拓展欧几里得解)
另外g^t=a可以由离散对数求出
给定newx, k, m, 方程 (x^k)%m=newx, 求在模m意义下的所有解x。
限制：
0 <= newx, m, k <= 1.5*10^15; m是素数。
/*hdu 3930 题意： 给定newx, k, m, 方程 (x^k)%m=newx, 求在模m意义下的所有解x。 限制： 0 <= newx, m, k <= 1.5*10^15; m是素数。 思路： N次剩余 */ #include #include #include #include #include #include using namespace std; #define LL __int64 #define PB push_back LL mul(LL a,LL b,LL m){ LL ret = 0; a %= m; while(b){ if(b & 1) ret = (ret + a) % m; a = (a + a) % m; b >>= 1; } return ret; } LL a_b_MOD_c(LL a,LL b,LL m){ LL ret = 1; a %= m; while(b){ if(b&1) ret = mul(ret,a,m); a = mul(a,a,m); b >>= 1; } return ret; } LL ext_gcd(LL a,LL b,LL &x,LL &y){ if(b==0) { x=1, y=0; return a; } LL ret= ext_gcd(b,a%b,y,x); y-= a/b*x; return ret; } vector a; bool g_test(LL g,LL p){ for(LL i=0;i (y*N)%(p-1)=t (此方程可以由拓展欧几里得解) 另外g^t=a可以由离散对数求出 */ vector residue(LL p, LL N, LL a){ LL g = pri_root(p); g %= p; LL m = log_mod(g, a, p); vector ret; if(a == 0){ ret.PB(0); return ret; } if(m == -1) return ret; LL A = N, B = p - 1, C = m, x, y; LL d = ext_gcd(A, B, x, y); if(C % d != 0) return ret; x = x * (C / d) % B; LL delta = B / d; for(int i = 0; i < d; ++i){ x = ((x + delta) % B + B) % B; ret.PB(a_b_MOD_c(g, x, p)); } sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } int main(){ int cas = 0; LL k,m,newx; while(scanf("%I64d%I64d%I64d",&k, &m, &newx)!=EOF){ vector ans; ans = residue(m,k,newx); printf("case%d: ",++cas); if(ans.size()==0) puts("-1"); for(int i = 0; i < ans.size(); ++i) printf("%I64d ",ans[i]); } return 0; }

热门文章