ๅช็ปณๅญ 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
}