publicclassSolution{ publicintcuttingRope(int n){ if (n <= 3) { return n - 1; } int a = n / 3; int b = n % 3; if (b == 2) { return (int) (quickPow(3, a) * b % 1000000007); } else { return (int) ((quickPow(3, a - 1) * (b + 3)) % 1000000007); } }
// private long quickPow(int x, int n) { // if (n == 0) { // return 1; // } // long y = quickPow(x, n / 2); // return (n & 1) == 1 ? (y * y * x) % 1000000007 : (y * y) % 1000000007; // }
privatelongquickPow(int x, long n){ long res = 1; long tt = x; while (n != 0) { if ((n & 1) == 1) { res *= tt; res %= 1000000007; } tt *= tt; tt %= 1000000007; n /= 2; } return res; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution{ publicintcuttingRope(int n){ if(n == 2) { return1; } if(n == 3){ return2; } int mod = (int)1e9 + 7; long res = 1; while(n > 4) { res *= 3; res %= mod; n -= 3; } return (int)(res * n % mod); } }
class Solution { public int integerBreak(int n) { if(n <= 3) return n - 1; int a = n / 3, b = n % 3; if(b == 0) return (int)Math.pow(3, a); if(b == 1) return (int)Math.pow(3, a - 1) * 4; return (int)Math.pow(3, a) * 2; } }
