[算法]从 CU 抄过来的数学题一个。

sunmoon1997

编写一个程序计算 3 ^ 1000 mod 7 的值。语言不限。

pointer

3^6=1 (mod 7)
so, 3^(1000)=3^(1000%6)=3^4=81=4 (mod 7)

wide288

1. 
   
2. main()
   
3. {
   
4.   int n = 0;
   
5.   long result = 0;
   
6.   
   
7.   result = 3*3;
   
8.   for(;n<1000;n++){
   
9.     result =* 3;
   
10.   }
    
11.   while(result >= 7){
    
12.     result =- 7;
    
13.   }
    
14. 
    
15.   printf("Value is %d \n", result);
    
16. }
    

复制代码

jhuangjiahua

>>> a=3**1000%7
>>> a
4

soloforce

1. 
   
2. ~ $  calc
   
3. C-style arbitrary precision calculator (version 2.11.5t4.5)
   
4. Calc is open software. For license details type:  help copyright
   
5. [Type "exit" to exit, or "help" for help.]
   
6. 
   
7. > 3^1000%7
   
8.         4
   
9. >
   

复制代码

还是我的代码比较精简啊

arxor

就这题来说, 二楼的最好....
但如果3换成n, 1000换成m,
要在O(log(m))内解决的...
4楼和5楼的复杂度是多少?

PS:不妨求第200000000个fib数mod 89999931的值吧

Yuri

好孩子,多来这里发些东西.我没上过学,不懂这些东西得.可以随便蒙.蒙好了给你加精!

pointer

Post by arxor

PS:不妨求第200000000个fib数mod 89999931的值吧

一个线性模数列肯定是周期的(这不一定纯)
而89999931= 3*7*293*14627
所以只要求其模这些数的值.

arxor

这个方法...^_^如果是大质数呢?
而且m可以大到 2^63 - 1

Post by pointer
一个线性模数列肯定是周期的(这不一定纯)
而89999931= 3*7*293*14627
所以只要求其模这些数的值.

pointer

这个方法...^_^如果是大质数呢?
而且m可以大到 2^63 - 1

我没有好办法.

一个方法是对F_n的n分解成2进制表示,这样大约只需要求O(log_2(n))次.

另一个一半的方法是对5是其二次剩余的质数p(50%的), 可以在Z_p里解\sqrt(5), 这样
将F_n的通项公式化成Z_p里的两个整数幂和. 整数幂对一个质数的模好求一些.