欧拉定理的简单应用

题目描述：

Description
大家都知道斐波拉契数列，f[1] = f[2] = 1,f[N] = f[N-1]+f[N-2],现在小泽想知道（x^f[N]）%100003。

Input
输入x，N（1<=x<=10^5, 1<=N<=10^5）

Output
输出（x^f[N]）%100003。

Sample Input 1
2 1
2 2

Sample Output 1
2
2

解题思路：

众所周知斐波那契的第1e5项实在是太太太太大了，还要计算以它为指数以x为底数的结果，属实是离谱住了。但是既然最后要对100003求余，那么我们不如要想个办法，找到和这个“离谱数”同余的一个数。

根据我们小学二年级学的欧拉定理可知，当x与m互质的时候，x^(φ(m))同余1(mod m) 。因为100003为质数，所以φ(100003)=100003-1=100002。因此我们在进行斐波那契数列计算的时候就可以让每一个数都模100002，再在快速幂的过程中每次都模100003就可以了。

当然，因为100003恰好是质数，所以这其实也就是费马小定理。费马小定理本身就是欧拉定理的一个特殊情况。

代码：

#include
using namespace std;
long long power(long long x, long long n) 
{	//快速幂long long ans=1;while (n>0) {if (n&1) ans=ans*x%100003;//n&1等价于 n%2==1n>>=1;//等价于n=n/2x=(x*x)%100003;}return ans;
}
long long f[100005];
int main()
{f[0]=1;f[1]=1;long long i,x,n;for(i=2;i<100005;i++)f[i]=(f[i-1]+f[i-2])%100002;while(cin>>x>>n)cout<<power(x,f[n-1])<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！