ๅ‰ช็ปณๅญ II ๐ŸŒŸ๐ŸŒŸ๐ŸŒŸไธญ็ญ‰

่ฏพๅŽไฝœไธš

้—ฎ้ข˜ๆ่ฟฐ

ๅŽŸๆ–‡้“พๆŽฅ๏ผšๅ‰‘ๆŒ‡ Offer 14- II. ๅ‰ช็ปณๅญ II

็ป™ไฝ ไธ€ๆ น้•ฟๅบฆไธบ n ็š„็ปณๅญ๏ผŒ่ฏทๆŠŠ็ปณๅญๅ‰ชๆˆๆ•ดๆ•ฐ้•ฟๅบฆ็š„ m ๆฎต๏ผˆmใ€n้ƒฝๆ˜ฏๆ•ดๆ•ฐ๏ผŒn>1ๅนถไธ”m>1๏ผ‰๏ผŒๆฏๆฎต็ปณๅญ็š„้•ฟๅบฆ่ฎฐไธบ k[0],k[1]…k[m – 1] ใ€‚่ฏท้—ฎ k[0]k[1]…*k[m – 1] ๅฏ่ƒฝ็š„ๆœ€ๅคงไน˜็งฏๆ˜ฏๅคšๅฐ‘๏ผŸไพ‹ๅฆ‚๏ผŒๅฝ“็ปณๅญ็š„้•ฟๅบฆๆ˜ฏ8ๆ—ถ๏ผŒๆˆ‘ไปฌๆŠŠๅฎƒๅ‰ชๆˆ้•ฟๅบฆๅˆ†ๅˆซไธบ2ใ€3ใ€3็š„ไธ‰ๆฎต๏ผŒๆญคๆ—ถๅพ—ๅˆฐ็š„ๆœ€ๅคงไน˜็งฏๆ˜ฏ18ใ€‚

็ญ”ๆกˆ้œ€่ฆๅ–ๆจก 1e9+7๏ผˆ1000000007๏ผ‰๏ผŒๅฆ‚่ฎก็ฎ—ๅˆๅง‹็ป“ๆžœไธบ๏ผš1000000008๏ผŒ่ฏท่ฟ”ๅ›ž 1ใ€‚

็คบไพ‹ 1๏ผš

่พ“ๅ…ฅ: 2
่พ“ๅ‡บ: 1
่งฃ้‡Š: 2 = 1 + 1, 1 ร— 1 = 1
็คบไพ‹ 2:

่พ“ๅ…ฅ: 10
่พ“ๅ‡บ: 36
่งฃ้‡Š: 10 = 3 + 3 + 4, 3 ร— 3 ร— 4 = 36

ๆ็คบ๏ผš

2 <= n <= 1000

ไปฃ็ ๅฎž็Žฐ

Java

class Solution {
    //ๅ–ๆจก๏ผš่ฆ่ฎฐไฝๆ€Žไนˆๅ–ๆจก
    public int cuttingRope(int n) {
        int res = n / 3;
        int mod = n % 3;
        int p = 1000000007;

        if(n <= 2){
            return 1;
        }

        if(n <= 3){
            return 2;
        }

        if(mod == 0){
            return (int)pow(3, res);
        }else if(mod == 1){
            return (int)(pow(3, res - 1) * 4 % p);
        }else{
            return (int)(pow(3, res) * 2  % p);
        }
    }

    // a^n%p
    long pow(int a, int n){
        int p = 1000000007;
        long res = 1;

        for(int i = 1; i <= n; i++){
            res = res * a % p;
        }

        return res;
    }

}

Python

class Solution:
    def cuttingRope(self, n):
        res = n // 3
        mod = n % 3
        p = 1000000007

        if n <= 2:
            return 1

        if n <= 3:
            return 2

        if mod == 0:
            return 3 ** res % p
        elif mod == 1:
            return (3 ** (res - 1) * 4) % p
        else:
            return (3 ** res * 2) % p

C++

class Solution {
public:
    int cuttingRope(int n) {
        int res = n / 3;
        int mod = n % 3;
        int p = 1000000007;

        if (n <= 2) {
            return 1;
        }

        if (n <= 3) {
            return 2;
        }

        if (mod == 0) {
            return pow(3, res);
        } else if (mod == 1) {
            return (pow(3, res - 1) * 4) % p;
        } else {
            return (pow(3, res) * 2) % p;
        }
    }

    long pow(int a, int n) {
        int p = 1000000007;
        long res = 1;

        for (int i = 1; i <= n; i++) {
            res = (res * a) % p;
        }

        return res;
    }
};

Go

func cuttingRope(n int) int {
    res := n / 3
    mod := n % 3
    p := 1000000007

    if n <= 2 {
        return 1
    }

    if n <= 3 {
        return 2
    }

    if mod == 0 {
        return pow(3, res)
    } else if mod == 1 {
        return (pow(3, res-1) * 4) % p
    } else {
        return (pow(3, res) * 2) % p
    }
}

func pow(a, n int) int {
    p := 1000000007
    res := 1

    for i := 1; i <= n; i++ {
        res = (res * a) % p
    }

    return res
}

ๅ‘่กจ่ฏ„่ฎบ

ๅŽๆ‰่ƒฝ่ฏ„่ฎบ