应该是gcd(a,p)==1,还有如果不满足条件应该怎么处理啊
by 如我西沉 @ 2017-10-22 01:28:01
两个不同的啊= =
欧拉定理 $a^b \equiv a^{b \, mod \, \phi(p)},gcd(a,p)=1$
Ext欧拉定理$a^b \equiv a^{b \, mod \, \phi(p)+p},gcd(a,p) \in N^+,\phi(p) \leq b$
上帝与集合的正确用法用的是欧拉定理,当然要$gcd(a,p)=1$。
而相逢是问候不保证互质,因此要用Ext欧拉定理。
by CSHwang @ 2017-10-22 13:50:59
@[CSHwang](/space/show?uid=42109)
那道题的指数不是无限个2吗,那不就大于ϕ(p)应该用扩展欧拉定理吗?
by ibilllee @ 2017-10-23 18:28:03
@[ibilllee](/space/show?uid=29892)
用扩欧当然也是行的。
但是上帝那题可以通过提取2的幂转换成互质的情况,用欧拉定理推导更方便。
by CSHwang @ 2017-10-23 20:33:20
@[CSHwang](/space/show?uid=42109) 哦是这样啊,谢谢,困扰了我很久
by ibilllee @ 2017-10-23 22:04:08