主题：求大虾教我模运算
389064181
[专家分：0] 发布于 2012-12-01 01:33:00
Hint:
1、1秒钟内，普通计算机大概处理10^8次运算。题目中的数据量如果用循环语句逐次累加将会使运行时间过长而返回“超时错误” (Time Limit Exceeded)，关于算法的复杂度具体可以看题目“ACM不得不知道的事儿(1)”。
2.模运算的部分性质
(a + b) % m = (a % m + b % m) % m;
(a * b) % m = ((a % m) * (b % m)) % m;
Input
输入包含多组数据，每组数据包含一个正整数n (1 <= n <= 2*10^8)。
Output
对于每组数据，由于结果可能非常大。输出2的n次方除以100000007取余（就是模100000007）的结果.
Sample Input
5
10
Sample Output
32
1024
回复列表 （共1个回复）
沙发
bruceteen [专家分：42660] 发布于 2012-12-01 10:28:00
先考虑 100000007 这个数
因为 2^27=134217728 堪堪大于100000007，(2^27)%100000007=34217721
所以 (2^n)%100000007 == ( 34217721^(n/27) * 2^(n%27) )%100000007
对于 2^(n%27)，很简单就是将1左移(n%27)位
现在考虑 34217721^(n/27)，用更一般的形式就是a^b，这个问题你可以Google一下“快速幂”
但这其中还有一个问题，两个小于100000007的数相乘最大为10000001200000036，超过了uint32_t的表示范围，如果用C++11标准中的unsigned long long当然没问题，但我估计这道题将这也作为一个考点，也就是不让你用uint64_t，你可以用“快速幂”类似的方法
对于 (a*b)%c，其中a,b皆小于100000007
可以用 uint32_t的最大值除以a，等到d，也就是a*d是不溢出的，……
算了，优化太多，你反而看不懂，我写个不优化的
[code=c]
typedef unsigned int uint32_t;
// (a*b)%c
uint32_t quick_mul( uint32_t a, uint32_t b, uint32_t c )
{
uint32_t r = 0;
for( uint32_t t=a; b; b>>=1 )
{
if( b&1 )
r = (r+t)%c;
t = (t+t)%c;
}
return r;
}
// (a^b)%c
uint32_t quick_pow( uint32_t a, uint32_t b, uint32_t c )
{
uint32_t r = 1;
for( uint32_t t=a; b; b>>=1 )
{
if( b&1 )
r = quick_mul(r,t,c);
t = quick_mul(t,t,c);
}
return r;
}
#include <iostream>
//#include <iomanip>
//#include <ctime>
using namespace std;
int main()
{
//clock_t c = clock();
cout << quick_pow(2,5,100000007) << endl;
cout << quick_pow(2,10,100000007) << endl;
cout << quick_pow(2,200000000,100000007) << endl;
//clock_t c2 = clock();
//c = clock() - c;
//cout << (c/CLOCKS_PER_SEC) << '.' << setfill('0') << setw(3) << (c%CLOCKS_PER_SEC*1000) << endl;
}
[/code]
我来回复
您所在位置：