模运算问题求解

殘影

Hint:
1、1秒钟内，普通计算机大概处理10^8次运算。题目中的数据量如果用循环语句逐次累加将会使运行时间过长而返回“超时错误” (Time Limit Exceeded)
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. #include <stdio.h>
   
2. #define DIVIDE_NUM 100000007
   
3. 
   
4. unsigned int get_result( unsigned int n );
   
5. int main(void) {
   
6.         unsigned int n;
   
7.         while( scanf( "%u", &n ) !=EOF )
   
8.                 printf("%u\n", get_result(n) );
   
9.         return 0;
   
10. }
    
11. 
    
12. unsigned int get_result( unsigned int n ) {
    
13.         if( n < sizeof(unsigned int)*8 )
    
14.                 return (1<<n)%DIVIDE_NUM;
    
15.         return ( get_result( n>>1 ) * get_result( n - n>>1 ) )%DIVIDE_NUM;
    
16. }

复制代码

℡.xiao敏

又一位纠结专研的朋友……给你顶，不懂

wangyexin

使用快速幂，也就是二分可以使时间复杂度降到log2(n)应该就可以过了

迷失的农民

想了半天也没推导出公式，坐等高手指导。

殘影

仰望天上的光 发表于 2012-12-1 10:39

                               
登录/注册后可看大图

不行哦 这个有错

仰望天上的光

殘影 发表于 2012-12-1 12:43

                               
登录/注册后可看大图

不行哦 这个有错

1. #include <stdio.h>
   
2. 
   
3. #define DIVIDE_NUM 100000007
   
4. 
   
5. 
   
6. unsigned int get_result( unsigned int n );
   
7. 
   
8. int main(void) {
   
9. 
   
10.         unsigned int n;
    
11. 
    
12.         while( scanf( "%u", &n ) !=EOF )
    
13.                 printf("%u\n", get_result(n) );
    
14. 
    
15.         return 0;
    
16. 
    
17. }
    
18. 
    
19. 
    
20. unsigned int get_result( unsigned int n ) {
    
21. 
    
22.         //if( n < sizeof(unsigned int)*8 )
    
23.                 if( n < sizeof(unsigned int)*8/2 )
    
24.                 return (1<<n)%DIVIDE_NUM;
    
25. 
    
26.         return ( get_result( n>>1 ) * get_result( n - n>>1 ) )%DIVIDE_NUM;
    
27. 
    
28. }

复制代码

修改一行

殘影

仰望天上的光 发表于 2012-12-1 13:09

                               
登录/注册后可看大图

修改一行

还是不行 从16次方开始就出错了

殘影

wangyexin 发表于 2012-12-1 10:35

                               
登录/注册后可看大图

使用快速幂，也就是二分可以使时间复杂度降到log2(n)应该就可以过了

能指教一下嘛？

wangyexin

我看不到你的回复

殘影

wangyexin 发表于 2012-12-1 19:51

                               
登录/注册后可看大图

我看不到你的回复

我说的是让你赐教一下。。。

wangyexin

1. a^k%m
   
2. long mod(long a,long k,long m)
   
3. {
   
4.     long b=1;
   
5.     while(k>=1)
   
6.     {
   
7.          if(k%2 == 1)b = a*b%m;
   
8.          a = a*a%m;
   
9.          k = k/2;
   
10.     }
    
11.     return b;
    
12. }

复制代码

代码没在编译器里运行，不一定能编译通过，但是大体算法就是这样了