学步园

题目地址：点击打开链接

题目大意：很容易得到2^(n-1)%M

题目分析：由于n非常大，所以想办法快速幂，很容易T

1.第一个方案就是想起:FZU 1759点击打开链接

相关资料见：证明http://blog.csdn.net/u011613321/article/details/10208699

                        欧拉公式证明：http://wenku.baidu.com/view/7124c406b52acfc789ebc9ef.html###很有意思

 但是！！！！这个方案死都T，这是什么情况啊，关键是我还将M=1e+7的phi直接带入啊

附上代码，欢迎斧正～～～，怎么会T?

结果……学姐帮忙看了下才发现，输入结束有误！！

～由于n>=1所以根本不会出现0，在样例完结时程序无法退出

#include<cstdio>
#include<cstring>

typedef long long LL;

char b[1000010];
LL quick_pow(LL x,LL y,LL p)
{
    LL ans=1;
    for (;y;y>>=1)
    {
        if (y&1) ans=(LL)ans*x%p;
        x=(LL)x*x%p;
    }
    return ans;
}
LL c=1e9+7,phi=1e9+6;//由于c为质数，所以phi很容易的为c-1，否则要用
int main()
{
    LL a=2,x,y,k;
    while (1)
    {
        scanf("%s",b);
        if(b[0]=='0')/////-这儿出错了～～由于n>=1所以根本不会出现0，在样例完结时程序无法退出
           break;
        x=y=0;
        LL len=strlen(b);
        for (LL i=0;i<len;i++)
        {
            x=x*10+b[i]-'0';
            if (y==0&&x>=phi) y=phi;
            x%=phi;
        }
        k=(x+y-1+phi)%phi;//出现减法，所以为了防止负数出现
        printf("%lld\n",quick_pow(a,k,c));
    }
    return 0;
}

所以代码更正后：

#include<cstdio>
#include<cstring>

typedef long long LL;

char b[1000010];
LL quick_pow(LL x,LL y,LL p)
{
    LL ans=1;
    for (;y;y>>=1)
    {
        if (y&1) ans=(LL)ans*x%p;
        x=(LL)x*x%p;
    }
    return ans;
}
LL c=1e9+7,phi=1e9+6;//由于c为质数，所以phi很容易的为c-1，否则要用
int main()
{
    LL a=2,x,y,k;
    while (scanf("%s",b)!=-1)
    {
        x=y=0;
        LL len=strlen(b);
        for (LL i=0;i<len;i++)
        {
            x=x*10+b[i]-'0';
            if (y==0&&x>=phi) y=phi;
            x%=phi;
        }
        k=(x+y-1+phi)%phi;//出现减法，所以为了防止负数出现
        printf("%I64d\n",quick_pow(a,k,c));
    }
    return 0;
}

哭死了，一定要读题仔细啊

为了方便，顺便附上欧拉公式的代码

  
LL eular(LL k)  
{  
    LL s=1;  
    for (LL i=2;i*i<=k;i++)  
    {  
        if (k%i==0)  
        {  
            k=k/i,s*=(i-1);  
            while (k%i==0)  
            k=k/i,s*=i;  
        }  
    }  
    if (k>1) s*=k-1;  
    return s;  
} 

2.回头想想，这么大的n必然是循环的否则一定会T 啊，循环节为(1e9+6)/2.
最后附上AC代码

    #include<cstdio>  
    #include<cstring>  
    #include<algorithm>  
    using namespace std;  
   
        
    const int MOD = 1e9 + 7;  
      
    char str[100006];  
      
    __int64 quick_mod(__int64 k)  
    {  
      __int64 ans = 1;  
       __int64 a = 2;  
        while(k)  
        {  
            if(k&1) ans = (ans*a)%MOD;  
            a = (a*a)%MOD;  
            k >>= 1;  
        }  
        return ans;  
    }  
      
    int main()  
    {  
        while(~scanf("%s",str))  
        {  
            int len = strlen(str);  
            __int64 k = 0;  
            for(int i = 0;i<len;i++)  
                k = (k*10 + str[i] - '0')%500000003;  
            k = (k -1 + 500000003)%500000003;  
            printf("%I64d\n",quick_mod(k));  
        }  
        return 0;  
    }

总结：有些优秀的模板不是每到题都适用，重要的是能随机应变。