字节笔试题，求大数对(1e9+7)值取模结果

骑猪看日落 2022-12-09 02:40 104阅读 0赞

### 字节笔试题 ###

*  求2的100万次方对(1e9+7)取模的结果
 *   *  使用分治法

# 求2的100万次方对(1e9+7)取模的结果 #

**提示** A=B\*C，则 A   m o d   x = ( ( B   m o d   x ) ) × ( C   m o d   x ) )   m o d   x A\\bmod x = \\left( \{\\left( \{B\\bmod x\} \\right)) \\times \\left( \{C\\bmod x\} \\right)\} \\right)\\bmod x Amodx=((Bmodx))×(Cmodx))modx

## 使用分治法 ##

2 1000000 = 2 500000 × 2 500000 \{2^\{1000000\}\} = \{2^\{500000\}\} \\times \{2^\{500000\}\} 21000000=2500000×2500000

*最开始根本没有想到用分治法，**简直太菜**，考完了才想到，当时只想到用**递归**，但是没有从分治的角度想问题，从1开始尝试2的多少次方可以对(1e9+7)取模。笔试结束后回宿舍好好想了想，为啥不用**分治法**，话不多说，上代码吧*。

import math
    
    def merge(array):
        """ merge @para: array, list """
        res = 1
        for temp in array:
            res = int((res*temp)%(1e9+7))
        return res
    
    def divide_and_conquer(num1, num2):
        """ 用分治法求(2^100w)%(1e9+7) @para: num1,数字1 @para: num2,次方 """
        if (num2==1) or (num2==0):
            temp = num2
            return int(math.pow(num1,temp)%(1e9+7))
        lst = [int(num2/2), num2 - int(num2/2)]
        y_res = list()
        for i in range(2):
            y_res.append(divide_and_conquer(num1, lst[i]))
        return merge(y_res)
    
    
    if __name__ == "__main__":
        print(divide_and_conquer(2, 1000000))

发表评论取消回复

表情：

评论列表（有 0 条评论，104人围观）

还没有评论，来说两句吧...

相关阅读

相关［笔试题］快乐数

１问题描述编写一个算法来判断一个数是否为快乐数快乐数定义：对于一个正整数，每一次将该数替换为它每个位置数字的平方和，重复，如果能变到１就是快乐数否则就不是快乐数

蔚落/ 2023年06月15日 13:24/ 0 赞/ 14 阅读

相关【笔试题】相似数

map，0和null不是一码事。注意在线编程别System import com.sun.org.apache.bcel.internal.generic.NE

淩亂°似流年/ 2023年03月01日 13:40/ 0 赞/ 15 阅读

相关 java1e6,大组合数取模之lucas定理模板,1<=n<=m<=1e9,11e6，p必须为素数

typedef long long ll; /\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ 大组合数取模之lucas定理模板,1<=n<=m<=1e

太过爱你忘了你带给我的痛/ 2023年01月15日 15:22/ 0 赞/ 93 阅读

相关字节笔试题，求大数对(1e9+7)值取模结果

字节笔试题求2的100万次方对(1e9+7)取模的结果使用分治法求2的100万次方对(1e9+7)取模的结果提示 A=B\C，则 A

骑猪看日落/ 2022年12月09日 02:40/ 0 赞/ 105 阅读

相关 python取模1e9+7_python学习笔记(1

关于python数据类型及变量 python中提供了整数、浮点数、字符串、布尔值 1.整数：可以处理任意大小的整数、又是也会使用十六进制数来表示 2.浮点：浮点数也就是

刺骨的言语ヽ痛彻心扉/ 2022年10月23日 01:53/ 0 赞/ 563 阅读

相关字节笔试题（含答案）

[个人博客][Link 1]欢迎访问 > 总结不易，如果对你有帮助，请点赞关注支持一下 > 微信搜索程序dunk，关注公众号，获取博主的数据结构与算法的代码笔记目录

- 日理万妓/ 2022年10月16日 11:25/ 0 赞/ 321 阅读

相关数串求最大值

![Center][]![Center 1][] 一、解法一 import java.util.; public class Main {

Love The Way You Lie/ 2022年05月27日 23:00/ 0 赞/ 241 阅读

相关 spark笔试题1

1. Spark 的四大组件下面哪个不是 (D ) A.Spark Streaming B Mlib C Graphx D Spark R 2.下面哪个端口不是

布满荆棘的人生/ 2022年01月13日 07:15/ 0 赞/ 500 阅读

相关 -1对256取模

今天看c++primer遇到了这个-1对256取模，负数取模还真的不清楚，所以查了查资料，供大家参考。（P33）原文：C++中，把负值赋给unsigned 对象是完全合法的

桃扇骨/ 2022年01月06日 08:13/ 0 赞/ 291 阅读

相关 Hive--笔试题05_1--求TopN

现在有一个面试题场景举例北京市学生成绩分析成绩的数据格式 exercise5\_1.txt 文件中的每一行就是一个学生的成绩信息。字段之间的分隔符是","

刺骨的言语ヽ痛彻心扉/ 2021年12月23日 20:11/ 0 赞/ 253 阅读