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("%I64dn",pow_mod(2,n));
    }
    return 0;
}