差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:i_dont_know_png:potassium:math_theory_revision_1 [2020/05/12 17:58]
potassium space
+++ 2020-2021:teams:i_dont_know_png:potassium:math_theory_revision_1 [2020/05/22 20:08] (当前版本)
potassium fix typos
@@ 行 11: / 行 11: @@
 由欧拉定理，若 $(a,n)=1$ ，则 $a^{\varphi(m)}\equiv 1\pmod m$ 。
-类似单位复根，数 $m$ 的原根 $g\in[1,m],(g,m)=1$ 满足 $\{g,g^2,...,g^{\varphi(m)}\}$ 构成模 $m$ 的一个既约剩余系。易得，对于质数 $m$ ，这个既约剩余系的取值范围为 $[1,m-1]$ 。
+类似单位复根，数 $m$ 的原根 $g\in[1,m],(g,m)=1$ 满足 $\{g,g^2,\ldots,g^{\varphi(m)}\}$ 构成模 $m$ 的一个既约剩余系。易得，对于质数 $m$ ，这个既约剩余系的取值范围为 $[1,m-1]$ 。
 原根的另一个定义是， $\forall p<\varphi(m), g^{\varphi(m)}\neq 1$ ，即 $\varphi(m)$ 是最小的让 $g^d\equiv 1\pmod m$ 的正整数 $d$ 。
@@ 行 45: / 行 45: @@
 设 $x=iB+t$ （或者 $x=iB-t$ ，都可），其中 $B$ 为块大小，先设为 $\left\lceil\sqrt c\right\rceil$ 。
-那么有 $a^{iB}\equiv b\cdot a^{-t}$ ，把右半部分预处理并扔进 map 里，从小到大枚举 $i\in[0,B]$ ，通过扩欧解出来右半边 $a^{-t}$ 应当取的值，查map判断，即可 $\mathcal{O}(\sqrt c)$ 求解。
+那么有 $a^{iB}\equiv b\cdot a^{-t}$ ，把右半部分预处理并扔进 map 里，从小到大枚举 $i\in[0,B]$ ，通过扩欧解出来右半边 $a^{-t}$ 应当取的值，查map判断，即可 $O(\sqrt c)$ 求解。
 ====== N次剩余 ======
@@ 行 51: / 行 51: @@
 即： $x^n\equiv a\pmod m$ ，给定 $m\in prime,n,a$ ，求出 $x$ 。
-前置芝士：扩欧，原根， $BSGS$
+前置芝士：扩欧，原根， BSGS
 模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=3930|HDU3930 Broot]]（数据范围有误，应为 $1e12$ 。数据较弱，提供[[https://paste.ubuntu.com/p/gC2QR6tFcq/|几组稍强数据]]）
@@ 行 59: / 行 59: @@
 设 $m$ 的一个原根为 $g$ ，由于 $a,x\in[0,m-1]$ ，必有 $x=0$ 或正整数 $y$ 满足 $g^{y}=x$ ， $a=0$ 或正整数 $z$ 满足 $g^{z}=a$ 。
-容易通过 $BSGS$ 求出 $z$ ，现在 $g^{yn}\equiv g^{z} \pmod m$ 式中只有 $y$ 未知。
+容易通过 BSGS 求出 $z$ ，现在 $g^{yn}\equiv g^{z} \pmod m$ 式中只有 $y$ 未知。
 式子等价于： $yn\equiv z\pmod \varphi(m)$ ，可以用扩欧求出 $y$ 的一个解 $y_0$ 。
@@ 行 65: / 行 65: @@
 设 $gcd=\gcd(n,\varphi(m))$ ， $y$ 的解集为 $\{k\in[0, gcd)|y_0+k\cdot \frac{\varphi(m)}{gcd}\}$ 。再根据此求出 $x$ 即可。
+<hidden 解法1>
+<code:c++>
+#include<cstdio>
+#include<algorithm>
+#include<queue>
+#include<map>
+#include<cstring>
+#include<cmath>
+#include<cstdlib>
+#include<set>
+#include<unordered_map>
+#include<vector>
+typedef long long ll;
+using namespace std;
+#define pb push_back
+#define mp make_pair
+#define fi first
+#define se second
+#define N 1238747
+#define hash HASH
+using namespace std;
+typedef long long ll;
+ll md(ll x,ll m){return x>=m?x-m:x;}
+ll mul(ll a,ll b,ll m){
+    ll ans=0;
+    a=(a%m+m)%m;b=(b%m+m)%m;
+    for(;b;b>>=1,a=md(a+a,m))if(b&1)ans=md(ans+a,m);
+    return ans;
+}
+ll qp(ll a,ll p,ll mod){
+	ll ans=1;
+	for(;p;p>>=1,a=mul(a,a,mod))if(p&1)ans=mul(ans,a,mod);
+	return ans;
+}
+//---------------BSGS----------------
+struct Triple{
+    ll x,y,z;
+    Triple(ll a,ll b,ll c) :x(a),y(b),z(c) {}
+};
+Triple exgcd(ll a,ll b){
+    if(b==0) return Triple(1,0,a);
+    const Triple last=exgcd(b,a%b);
+    return Triple(last.y,last.x-a/b*last.y,last.z);
+}
+int A,B,C;
+set<ll>S;
+unordered_map<ll,int>ma;
+ll bsgs(ll A,ll B,ll C){
+    ll sqrtn=ceil(sqrt(C)),base=1;
+    ma.clear();
+    for(int i=0;i<sqrtn;i++){
+        if(base)ma[base]=i;
+        base=mul(base,A,C);
+    }
+    ll i=0,j=-1,D=1;
+    S.clear();
+    for(;i<sqrtn;i++){
+        Triple res=exgcd(D,C);
+        const ll c=C/res.z;
+        res.x=(mul(res.x,(B/res.z),c)+c)%c;
+        if(ma.count(res.x)){
+       		j=ma[res.x];
+       		return (i*sqrtn+j);
+		}
+        D=mul(D,base,C);
+    }
+    return -1;
+}
+//------------sieve----------------
+#define M 1000000
+#define P 1000000
+int isnp[M],pri[P],cnt_prime;
+void sieve(){
+	int i,j;
+	isnp[0]=isnp[1]=1;
+	for(i=2;i<M;i++){
+		if(!isnp[i])pri[cnt_prime++]=i;
+		for(j=0;j<cnt_prime&&1LL*i*pri[j]<M;j++){
+			isnp[i*pri[j]]=1;
+			if(i%pri[j]==0)break;
+		}
+	}
+}
+//-------------pri factor------------
+vector<pair<ll,int>>pris;
+void get_pf(ll x){
+	int i;
+	pris.clear();
+	for(i=0;i<cnt_prime&&1LL*pri[i]*pri[i]<=x;i++){
+		if(x%pri[i]==0){
+			int count=0;
+			while(x%pri[i]==0)count++,x/=pri[i];
+			pris.pb(mp(pri[i],count));
+		}
+	}
+	if(x>1)pris.pb(mp(x,1));
+}
+//-----------primitive root-------------
+int jud_proot(int g,int index,ll d,ll p){
+	// optimized
+	int i;
+	for(i=0;i<pris.size();i++)if(qp(g,(p-1)/pris[i].first,p)==1)return 0;
+	return 1;
+	// origin
+	/*if(index==pris.size())return !(qp(g,d,p)==1&&d!=p-1);
+	ll tmp=1;int i;
+	ll pri=pris[index].fi,count=pris[index].se;
+	for(i=0;i<=count;i++){
+		if(!jud_proot(g,index+1,d*tmp,p))return 0;
+		tmp=tmp*pri;
+	}
+	return 1;*/
+}
+int get_proot(ll p){
+	int g=2;
+	while(!jud_proot(g,0,1,p))g++;
+	return g;
+}
+int main(){
+	ll n,p,a;
+	int cas=0,i;
+	sieve();
+	while(~scanf("%lld%lld%lld",&n,&p,&a)){
+		a%=p;
+		printf("case%d:\n",++cas);
+		if(!a){
+			if(n==0)printf("-1\n");
+			else printf("0\n");
+			continue;
+		}
+		get_pf(p-1);
+		int g=get_proot(p);
+		ll y=bsgs(g,a,p);
+		if(y==-1){printf("-1\n");continue;}
+		// nX+(p-1)Y=y
+		Triple tri=exgcd(n,p-1);
+		ll gcd=tri.z;
+		ll X=tri.x;
+		if(y%gcd){printf("-1\n");continue;}
+		vector<ll>ans;ans.clear();
+		ll a1=n/gcd,a2=(p-1)/gcd,a3=y/gcd;
+		//a1*X+a2*Y=a3 (mod a2), (a1,a2)=1
+		ans.pb((mul(X,a3,a2)+a2)%a2);
+		for(i=1;i<gcd;i++)ans.pb(ans[i-1]+a2);
+		for(i=0;i<gcd;i++)ans[i]=qp(g,ans[i],p);
+		sort(ans.begin(),ans.end());
+		for(i=0;i<gcd;i++)printf("%lld\n",ans[i]);
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
 ==== 解法2 ====
@@ 行 71: / 行 228: @@
 现在 $(g^{n})^{y}\equiv a \pmod m$ 式中只有 $y$ 未知。
-通过 $BSGS$ 可以求出所有符合要求的 $y$ ，但这里的 $BSGS$ 需要使用 ''%%map<int,vector>%%'' ，因为 $g^n$ 不是原根， $a^{t}$ 部分并非一对一关系。过后根据 $y$ 算出 $x$ 即可。
+通过 BSGS 可以求出所有符合要求的 $y$ ，但这里的 BSGS 需要使用 ''%%map<int,vector>%%'' ，因为 $g^n$ 不是原根， $a^{t}$ 部分并非一对一关系。过后根据 $y$ 算出 $x$ 即可。
+这两种解法都通过了原根进行转换，第一种方法由于没有使用较为复杂的 ''%%map%%'' ，常数比较小；第二种方法则更加简便、易写。
-这两种解法都通过了原根进行转换，[[https://paste.ubuntu.com/p/8pprk3zQvx/|第一种方法]]由于没有使用较为复杂的 ''%%map%%'' ，常数比较小；[[https://paste.ubuntu.com/p/yyhYMsXy7m/|第二种方法]]则更加简便、易写。
+<hidden 解法2>
+<code:c++>
+#include<cstdio>
+#include<algorithm>
+#include<queue>
+#include<map>
+#include<cstring>
+#include<cmath>
+#include<cstdlib>
+#include<set>
+#include<unordered_map>
+#include<vector>
+typedef long long ll;
+using namespace std;
+#define pb push_back
+#define mp make_pair
+#define fi first
+#define se second
+using namespace std;
+typedef long long ll;
+ll md(ll x,ll m){return x>=m?x-m:x;}
+ll mul(ll a,ll b,ll m){
+    ll ans=0;
+    a=(a%m+m)%m;b=(b%m+m)%m;
+    for(;b;b>>=1,a=md(a+a,m))if(b&1)ans=md(ans+a,m);
+    return ans;
+}
+ll qp(ll a,ll p,ll mod){
+	ll ans=1;
+	for(;p;p>>=1,a=mul(a,a,mod))if(p&1)ans=mul(ans,a,mod);
+	return ans;
+}
+//---------------BSGS----------------
+struct Triple{
+    ll x,y,z;
+    Triple(ll a,ll b,ll c) :x(a),y(b),z(c) {}
+};
+Triple exgcd(ll a,ll b){
+    if(b==0) return Triple(1,0,a);
+    const Triple last=exgcd(b,a%b);
+    return Triple(last.y,last.x-a/b*last.y,last.z);
+}
+set<ll>S;
+unordered_map<ll,vector<int>>ma;
+void bsgs(ll A,ll B,ll C,int g){
+    ll sqrtn=ceil(sqrt(C)),base=1;
+    ma.clear();
+    for(int i=0;i<sqrtn;i++){
+        if(base)ma[base].pb(i);
+        base=mul(base,A,C);
+    }
+    ll i=0,j=-1,D=1;
+    S.clear();
+    for(;i<sqrtn;i++){
+        Triple res=exgcd(D,C);
+        ll c=C/res.z;
+        res.x=(mul(res.x,B/res.z,c)+c)%c;
+        if(ma.count(res.x)){
+        	for(auto j:ma[res.x])
+ 		       	S.insert(qp(g,(i*sqrtn+j),C));
+		}
+        D=mul(D,base,C);
+     }
+}
+//------------sieve----------------
+#define M 1000005
+#define P 1000000
+int isnp[M],pri[P],cnt_prime;
+void sieve(){
+	int i,j;
+	isnp[0]=isnp[1]=1;
+	for(i=2;i<M;i++){
+		if(!isnp[i])pri[cnt_prime++]=i;
+		for(j=0;j<cnt_prime&&1LL*i*pri[j]<M;j++){
+			isnp[i*pri[j]]=1;
+			if(i%pri[j]==0)break;
+		}
+	}
+}
+//-------------pri factor------------
+vector<pair<ll,int>>pris;
+void get_pf(ll x){
+	int i;
+	pris.clear();
+	for(i=0;i<cnt_prime&&1LL*pri[i]*pri[i]<=x;i++){
+		if(x%pri[i]==0){
+			int count=0;
+			while(x%pri[i]==0)count++,x/=pri[i];
+			pris.pb(mp(pri[i],count));
+		}
+	}
+	if(x>1)pris.pb(mp(x,1));
+}
+//-----------primitive root-------------
+int jud_proot(int g,int index,ll d,ll p){
+	// optimized
+	int i;
+	for(i=0;i<pris.size();i++)if(qp(g,(p-1)/pris[i].first,p)==1)return 0;
+	return 1;
+	// origin
+	/*if(index==pris.size())return !(qp(g,d,p)==1&&d!=p-1);
+	ll tmp=1;int i;
+	ll pri=pris[index].fi,count=pris[index].se;
+	for(i=0;i<=count;i++){
+		if(!jud_proot(g,index+1,d*tmp,p))return 0;
+		tmp=tmp*pri;
+	}
+	return 1;*/
+}
+int get_proot(ll p){
+	int g=2;
+	while(!jud_proot(g,0,1,p))g++;
+	return g;
+}
+int main(){
+	ll n,p,a;
+	//freopen("in.txt","r",stdin);
+	int cas=0;
+	sieve();
+	while(~scanf("%lld%lld%lld",&n,&p,&a)){
+		a%=p;
+		printf("case%d:\n",++cas);
+		if(!a){
+			if(n==0)printf("-1\n");
+			else printf("0\n");
+			continue;
+		}
+		get_pf(p-1);
+		int g=get_proot(p);
+		//printf("%d\n",g);
+		ll bas=qp(g,n,p);
+		bsgs(bas,a,p,g);
+		if(!S.size())printf("-1\n");
+		else for(auto x:S)printf("%lld\n",x);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具