费马小定理与等比数列的求和（mod 质数）
费马小定理：任意整数a， a^p≡a (mod p)，p是质数。
定理：1.对a/b≡a*x (mod n)，则称x 为b的乘法逆元，记为b^-1。
2.当模数p为质数，且b与p互质（即b不为p的倍数）时，b的乘法逆元为b^(p-2)。
对2的简单证明：
b*b^-1≡1 （mod p）。①
由费马小定理，b^(p-1)≡1 (mod p)，b*b^-1*b^(p-1)≡1 (mod p)，即 b*b^（p-2）≡ 1 (mod p)。对比①，所以得到2的结论。
所以，对等比数列和公式 a*(q^n-1)/(q-1)，就可以用快速幂求得分母的逆元，然后乘上分子的模再取模。
对等比数列 1+a+a^2+a^3+……+a^n，结果对质数p取模，分两类情况讨论：
- a-1与p不互质，那么上面的定理2就不能使用了。但是可以发现，a%p≡1 (mod p)。所以原式就变成了 n+1。
- 若 a-1与p不互质，则根据等比数列公式，原式就为1*[a^(n+1)-1]%p *[(a-1)^(p-2)]%p。
这样，就在极短的时间内完成了等比数列的求和，主要的时间花费都集中在快速幂部分。
代码如下：
int qpow(int a,long long b,int mod)
{
int ans=1;
while(b>0)
{
if(b&1)ans=(long long)ans*a%mod;
a=(long long)a*a%mod;
b=b>>1;
}
return ans;
}
int main()
{
int a,n,p;
cin>>a>>n>>p;
int sum;
if((a-1)%p==0)
{
sum=n+1;
}
else
{
sum=qpow(a,(long long)n+1,p);
sum=(sum-1+p)%p;
sum=(long long)sum*qpow(a-1,p-2,p)%p;
}
cout<<sum;
}
Bonne continuation pour ton blog que je continue à suivre réguliérement.
Excellent article, thank you.
Merci pour le partage. Gwenneth Monroe Medardas
El vostre article és bonic. Berta Reade Levon
Esta debe ser la mejor colección de blogs sitio web que he encontrado a cabo. Kai Gibb Muir
Man kann jeden Tag etwas Neues hier lernen. Ich bin ein regelmäßiger für die meisten von denen Blogs, aber immer noch nicht um ein Paar von ihnen wissen. Ezmeralda Husain Udela
A excellent article, I just given this onto a colleague who was doing a analysis on this. And he ordered me lunch because I found it for him :). So let me rephrase that: Thankx for taking the time to talk about this, I feel strongly about it and enjoy learning more on this topic. If possible, as you become expertise, would you mind updating your blog with more info? It is extremely helpful for me. Robby Osbert McIntyre
I am just commenting to let you understand what a nice discovery our girl experienced viewing the blog. She mastered a lot of pieces, including what it is like to possess a wonderful teaching spirit to have most people very easily fully understand specified advanced matters. You actually exceeded her expectations. Many thanks for delivering these valuable, safe, edifying not to mention fun tips about that topic to Julie. Lynett Adams Berne
Você tem um fabuloso blog de graças. Silvia Haze Leighton
Vous avez relevé des détails intéressants ! ps site décent. Edith Giovanni Tamer
J’ai lu plusieurs choses excellentes ici. Signet de prix définitivement pour revisiter. Je me demande combien de fois vous tentez de créer un excellent site Web informatif. Susie Martainn Marthena
Thank you for any other magnificent post. Where else may anybody get that type of info in such
an ideal approach of writing? I have a presentation next week, and I’m at the search for such information.