显然不唯一。例如,$x_0=px$ 也行。
最小值不需要,因为逆元是用来取模的,一 $mod$ 就没了
by 超级玛丽王子 @ 2020-10-24 15:51:43
@[我爱Chtholly](/user/372299) 谢谢大佬,那么就是说,乘法逆元是用来分数取模的,取模之后只有唯一值?
by zhanghzqwq @ 2020-10-24 15:53:30
然后就是比如说crt中用到的乘法逆元不是用来取模的,那就取最小值是吗
by zhanghzqwq @ 2020-10-24 15:54:48
@[zhanghanzhang](/user/219668) 我不知道他说的是什么意思(
在模意义下,一个数的逆元除零以外存在且唯一,证明忘了(
by 木木! @ 2020-10-24 15:56:29
@[zhanghanzhang](/user/219668) 唯一性证明:
假设有一个非零数 $x$ 有两个逆元 $a$ 和 $b$,则有:
$$
ax\equiv1\pmod p
$$
$$
bx\equiv1\pmod p
$$
则
$$
axa\equiv bxa\equiv1\pmod p
$$
然后由 $xa\neq 0$ 消去 $xa$,即可得 $a=b$。
存在性可以用计算逆元的算法证明(
by 木木! @ 2020-10-24 16:00:25
@[zhanghanzhang](/user/219668) x%p是唯一的
by Stinger @ 2020-10-24 16:02:32
@[木木!](/user/49458) 如果不对逆元取模,逆元不唯一;中国剩余定理中不需要乘法逆元啊 @[zhanghanzhang](/user/219668)
by 超级玛丽王子 @ 2020-10-24 16:04:35
@[zhanghanzhang](/user/219668) 只需要 exgcd
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[11],b[11],N,M=1,Ans=0;
ll read() {
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
ll x=0;
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
void Read() {
N=read();
for(ll i=1;i<=N;i++) a[i]=read(),b[i]=read(),M*=a[i];
}
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
if(!b) d=a,x=1ll,y=0ll;
else {
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
void Intchina() {
ll Mi,x,y,i,d;
for(i=1;i<=N;i++) {
Mi=M/a[i];
exgcd(Mi,a[i],d,x,y);
Ans=((Ans+Mi*x*b[i])%M+M)%M;
}
printf("%lld\n",Ans);
return;
}
int main(void) {
Read();
Intchina();
return 0;
}
```
by 超级玛丽王子 @ 2020-10-24 16:05:28
@[木木!](/user/49458) 谢谢大佬,也就是说:
$ax\equiv bx\pmod{m}$
可以推出来$a=b$?
by zhanghzqwq @ 2020-10-24 16:05:34
@[我爱Chtholly](/user/372299) 哦对对对,我是在看crt第一篇题解的时候看见他说了乘法逆元,就去学了一下
by zhanghzqwq @ 2020-10-24 16:07:19