【学习笔记】简单数论-同余

• 特例：当 \(\gcd(c,p)=1,a \times c\equiv b \times c \pmod{p}\) 时，则 \(a \equiv b \pmod{p}\) 。

• 当 \(a\) 是 \(p\) 的倍数时，显然结论成立。
• 当 \(a\) 不是 \(p\) 的倍数时，不存在一组 \(x,y\) 满足 \(1 \le x,y<p,xa \equiv ya \pmod{p}\) 。因此 \(1 \sim p-1\) 所有数，乘以 \(a\) 之后对 \(p\) 取模，仍可得 \(1\) ~ \(p-1\) 所有数。则 \(\prod\limits_{i=1}^{p-1} i \equiv \prod\limits_{i=1}^{p-1} ai \pmod{p}\) ，易知其中 \(\prod\limits_{i=1}^{p-1} i\) 与 \(p\) 互质，则 \(\prod\limits_{i=1}^{p-1}a \equiv 1 \pmod{p}\) ，即 \(a^{p-1} \equiv 1 \pmod{p}\) 。等式两边同乘 \(a\) ，得到 \(a^p \equiv a \pmod{p}\) 。

• 若 \(\gcd(a,p)=1\) ，即 \(a\) 不是 \(p\) 的倍数，有 \(a^{p-1} \equiv 1 \pmod{p}\) 。
• 若 \(\gcd(a,p) \ne 1\) ，即 \(a\) 是 \(p\) 的倍数，有 \(a^{p-1} \equiv 0 \pmod{p}\) 。

• 证明：已知 \(2x \equiv 1 \pmod{2n+1}\) ，设 \(2x=(2n+1)k+1\) ，又因为 \(2x\) 为偶数， \(k\) 的最小正整数解为 \(1\) ，代入得 \(x=n+1\) 。

• 限制条件： \(\gcd(a,b)=1\) 。
• 设 \(ax=bk+1,y=-k\) ，原方程可改写为 \(ax+by=1\) ，用 \(exgcd\) 解得一组特解 \(x_0,y_0\) ，\(x\) 的最小正整数解为 \((x+b)\bmod b\) 。
• 时间复杂度为 \(O(\log \max(a,b))\) 。
• luogu P1082 [NOIP2012 提高组] 同余方程

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		ll d=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return d;
	}
}
int main()
{
	ll a,b,x=0,y=0;
	cin>>a>>b;
	exgcd(a,b,x,y);
	x=(x%b+b)%b;
	cout<<x<<endl;
}

const ll p=19260817;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		ll d=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return d;
	}
}
int main()
{
	ll a,c,d,x=0,y=0;
	c=read();
	a=read();
	d=exgcd(a,p,x,y);
	if(c%d==0)
	{
		x=(x*c/d)%p;
		x=(x%p+p)%p;
		cout<<x<<endl;
	}
	else
	{
		cout<<"Angry!"<<endl;
	}
	return 0;
}

ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	a%=p;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans%p;
}
int main()
{
	ll a,b;
	cin>>a>>b;
	cout<<qpow(a,b-2,b)<<endl;
}

ll inv[3000001];
int main()
{
	ll n,p,i;
	cin>>n>>p;
	inv[1]=1;
	cout<<"1"<<endl;
	for(i=2;i<=n;i++)
	{
		inv[i]=(p-p/i)*inv[p%i]%p;
		cout<<inv[i]<<endl;
	}
	return 0;
}

ll mul[3000001],invc[3000001],inv[3000001],w[3000001];//防止重名，此处的w[]即为上文的a[]
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans%p;
}
int main()
{
	ll n,p,i;
	cin>>n>>p;
	mul[0]=1;
	for(i=1;i<=n;i++)
	{
		w[i]=i;
		mul[i]=((mul[i-1]%p)*(w[i]%p))%p;
	}
	invc[n]=qpow(mul[n],p-2,p);
	for(i=n-1;i>=1;i--)
	{
		invc[i]=((invc[i+1]%p)*((w[i+1])%p))%p;
	}
	for(i=1;i<=n;i++)
	{
		inv[i]=((invc[i]%p)*(mul[i-1]%p))%p;
		cout<<inv[i]<<endl;
	}
	return 0;
}