JAVA大数问题

• • • 大数求余问题
    • 1.循环求余法
    • 2.快速幂求余法
    • 剪绳子的大数问题
  • 今日推歌

• 当求解x的a次幂时，可能会出现大数越界的问题，超出int32位，所以很多题目要求对结果进行1000000007的取余，这个数字在int32的范围之内
• 1000000007的平方超出了int32的范围，但是在long64的范围之内

思路：

(a+b)%c=(a%c+b%c)%c
a % c = ( a % c ) % c
( a b ) % c = [ ( a % c ) ( b % c ) ] % c

利用循环操作一次求得X的一次方，二次方，…，a次方对P的余数，保证每一轮中间求得的余数都在32位整数范围内：

def remainder(x,a,p):
	"""
	rem = x^a % p
	"""
	rem = 1
	for _ in range(a):
		rem = (rem * x) % p
	return rem

# 求 (x^a) % p —— 快速幂求余
def remainder(x, a, p):
    rem = 1
    while a > 0:
        if a % 2: rem = (rem * x) % p
        x = x ** 2 % p
        a //= 2
    return rem

循环求余：

// 求 (x^a) % p —— 循环求余法。固定搭配建议背诵
   public long  remainder(int x,int a,int p){  //x为底数，a为幂，p为要取的模
        long rem = 1 ;
        for (int i = 0; i < a; i++) {
            rem = (rem * x) % p ;   
        }
        return rem;
    }
class Solution {
   public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;

        long rem = 1, x = 3 ,a = n / 3;
        //直接套循环求余公式
        for(int i = 0; i < ((b == 1)?a-1:a); i++) { //b == 1代表余数为1的时候，需要单独取出一个3出来凑成2*2达到最大值效果
            rem = (rem * x) % p;
        }  
        if(b == 0) return (int)(rem % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 2 % p);
    }

快速幂求余：

这个比较难理解

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3;
        for(int a = n / 3 - 1; a > 0; a /= 2) {
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }
}

Python 代码： 由于语言特性，理论上 Python 中的变量取值范围由系统内存大小决定（无限大），因此在 Python 中其实不用考虑大数越界问题。
Java 代码： 根据二分法计算原理，至少要保证变量 x 和 rem 可以正确存储 1000000007^2，而 2^{64} > 1000000007^2 > 2^{32} ，因此我们选取 long 类型。

-----《互不打扰》陈之

还在念念不忘 是你给的好
故事很短 回忆却满是欢笑
如果当初 换你煎熬
你会不会体会 我的渺小
互不打扰 是我们最后的习惯
你的名字 是我一生的温暖
从此平淡 诸事无关