杭电3003

题意：PuPu有n层皮肤，每层皮肤都有2种状态：透明和不透明，每层皮肤如果能被太阳照射到，则被太阳照射一天后都会变换状态。PuPu在出生的时候，所有的皮肤都为不透明的，直到每一层的皮肤都有过变为透明状态的时候，PuPu也就长大了。问有n层皮肤的PuPu几天后能长大。

 

思路：数论。公式推导到最后为 ans = (2^(n-1)+1)%n。所以就用求(num^exp)%MOD的二分算法了，让时间复杂度为0(n)变为0(logn)。

 

#include<stdio.h>
__int64 n;

__int64 a_b_Mod_c(__int64 a, __int64 b, __int64 c)
   {
    int digit[64];                  
    int i, k;
 __int64 result = 1;         
    i = 0;
    while(b)
    {
        digit[i++] = b%2; //记下每次二分的状态！0 表示 x^2n=x^n * x^n  1表示x^(2n+1)=x^n * x^n * x;
        b >>= 1;
    }
    for(k = i-1; k >= 0; k--)
    {
        result = (result * result) % c;                
        if(digit[k] == 1)  //根据二分的结果来算！
        {
            result = (result * a) % c;                 
        }
    }
    return result;
}
main()
{
 __int64 d;
 while(scanf("%I64d",&n),n)
 {
 d=a_b_Mod_c(2,n-1,n)+1;
 printf("%I64d\n",d%n);
 }

}