hdu4704--sum--大数幂取模

本文主要是介绍hdu4704--sum--大数幂取模，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

做这道题学到了好多好多知识，想起了一些被遗忘的知识，收获还是很大的。

1.费马小定理的应用。首先说明一下什么是费马小定理：假如P是质数，且gcd(a,p)=1(即a，p互质)，则a^(p-1)===1（mod p）。

   应用为：若P为质数，且gcd(a,p)=1，则可以计算 a^n mod p的值。(n为一个无法用long long存下的大数(若不为大数直接用快速幂其实就可以了))

   因为a^(p-1)%p=1，所以a^((p-1)*k)%p也为1。所以a^n mod p=a^(n%(p-1))%p；

   所以就通过这样将n转化为一个在可接受范围内的数，然后在利用快速幂求出答案。

2.学会了一个知识，即在已知a mod b=x，x已知的情况下，怎样求出 (a-1) mod b的值。值即为 (x -1+b) mod b。

  ( 切记此时x的范围是0～b-1！否则值为((x-1)mod b+b) mod b )

3.学会了大数取模时的处理方法，即通过按位一位一位取模(每算一位记得乘以10)，因为模运算是可以拆分成 各个加法运算分别取模 然后加和再取模 的。

4.至于怎样得到答案为2^(n-1)这个结论的，参加离散数学书中关于排列组合中的挡板法。(2^(n-1)=C{n-1,0}+C{n-1,1}+......C(n-1,n-1))

以下是代码：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxlen=1e5+10;
const int M=1e9+7;
char a[maxlen];ll pow_mod(ll a,ll n)
{ll ans=1;while(n){if(n&1)ans*=a;if(ans>=M) ans%=M;a*=a;if(a>=M) a%=M;n>>=1;}return ans;
}
int main()
{while(~scanf("%s",a)){int len=strlen(a);ll n=0;for(int i=0;i<len;++i)//这里原来很SB的把len写成来strlen(a)，结果T了好久，真是SB的可以了。。。不过也长经验了，下次不会范这么2的错误了。n=(n*10+a[i]-'0')%(M-1);//这里的思想值得多多体会n=(n-1+M-1)%(M-1);pow_mod(2,n);printf("%I64d\n",pow_mod(2,n));}return 0;
}

这篇关于hdu4704--sum--大数幂取模的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---