hdoj/hdu 3003 Pupu(二分求(n^e)%m)

超级传送门：

http://acm.hdu.edu.cn/showproblem.php?pid=3003

题目大意：

Pupu有N层皮，每一层要么是透明，要么是不透明的，每天被太阳晒到的就会变一次，设刚出生都不透明，要全部皮都至少变过一次要多少天？

N<=20 结果很大，mod M

题目分析：

假设有一层要晒到太阳，必须前面都变成了透明。。。对不起啊，推导的那张纸被我丢掉了=。=

然后最后推出来，公式是：（2^(n-1)+1）%n

然后这次的重点是：求这种a^b %n怎么办

__int64 mod_exp(__int64 a,__int64 b0,__int64 n)//return a^b0 % n 
{ if( a > n ) a %= n; __int64  i, d = 1, b[35]; for( i=0; i < 35; ++i ){ b[i] = b0%2; b0 /= 2; if( b0 == 0 )  break; } //b[i]b[i-1]...b[0]为 b0的二进制表示 for( ;i >= 0; --i ){ d = (d*d)%n; if( b[i] == 1 )  d = (d*a)%n; } return d; 
}

多亏了二进制这个东西啊。。。。

下面就容易AC了：

#include
using namespace std;__int64 mod_exp(__int64 a,__int64 b0,__int64 n)//return a^b0 % n 
{ if( a > n ) a %= n; __int64  i, d = 1, b[35]; for( i=0; i < 35; ++i ){ b[i] = b0%2; b0 /= 2; if( b0 == 0 )  break; } //b[i]b[i-1]...b[0]为 b0的二进制表示 for( ;i >= 0; --i ){ d = (d*d)%n; if( b[i] == 1 )  d = (d*a)%n; } return d; 
}int main()
{int n;while(scanf("%d",&n) != EOF){if(n == 0) break;printf("%I64d\n",(mod_exp(2,(n-1),n)+1)%n);}return 0;
}

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