[Code ngắn nhất] SIMPLE_POWERS

Đề bài
Cho hai số nguyên dương a và b (a,b<10^9), thực hiện lần lượt các phép tính sau:

  • Đặt M=10^9 + 7;
  • Tính x=(a^b+b^a)%M;
  • Chuyển x sang nhị phân ta được số y;
  • Coi y ở cơ số 3, chuyển y sang hệ thập phân lấy dư khi chia cho M;

Ví dụ:

a=3, b=2
Ta sẽ có các phép tính sau:
x=(3^2+2^3)%M=17
y=10001
kết quả khi chuyển y tư cơ số 3 sang cơ số 10 là 82;

Yêu cầu viết hàm đề giải bài toán trên.

int Simple_powers(int a, int b) {

}

Đây là code ngắn nhất mà em có thể viết được, mong các anh chị góp ý thêm. (183 kí tự)

int64_t e, M=1e9+7, p(int x, int y)
{
    if( y == 0) return 1;
    e = p(x, y/2);
    return y&1? x*e%M*e%M : e*e%M;
}
int64_t t=0, i=0, Simple_powers(int a, int b) {
    a=p(a,b)+p(b,a);
    while(a%=M)
        t+=a%2*p(3,i++),
        a/=2;
    return t%M;
}

Links bài toán: https://codefights.com/challenge/nntw8bcTzebYRjBMh/main
Em cám ơn

1 Like

cái tính pow return long
simple_powers return int là đc 176 ký tự

cái y == 0 có thể thay bằng !y

Global variable theo mình biết tự gán bằng 0, nên 2 phép gán = 0 kia hơi dư.

Rút gọn lại còn 170 ký tự

3 Likes

Anh ơi, biến t rất lớn nên khai báo kiểu long.
Đây là code của anh:


long e, M=1e9+7, p(int x, int y)
{
    if(!y) return 1;
    e = p(x, y/2);
    return y&1? x*e%M*e%M : e*e%M;
}
long t, i, Simple_powers(int a, int b) {
    a=p(a,b)+p(b,a);
    while(a%=M)
        t+=a%2*p(3,i++),
        a/=2;
    return t%M;
}

Người đứng đầu chỉ cần 153 kí tự, không biết anh có thể qua mức đó?

1 Like

Cái hàm p thay = cái nùi này là đc 161 chars

long e, M=1e9+7, p(int x, int y) {
    return y ? e = p(x, y/2), y % 2 ? x * e%M * e%M : e * e%M : 1;
}
3 Likes

Anh giải thích giùm em chổ này không?

nó là thế này

if(y > 0) {
 e = p(x, x/2);
 e = y % 2 ? x * ...;
 return e;
} else return 1;
3 Likes

Cám ơn anh, code của anh lên hạng thứ 3 rồi đó :v:

2 Likes

Mình quỳ rồi :))
Thằng top làm gì mà ghê thế nhỉ.
Chắc nó có thuật pow đơn giản :joy:.

Ko rõ dùng pow cổ điển (vòng for) bị TLE ko nhỉ :?

2 Likes

sao cả chục ông top toàn 76 chars vậy :joy:

1 Like

Họ viết bằng Python nên ngắn :smile:

1 Like

Bài đó bắt viết bằng python mà. Nhưng mà mấy bạn trên kia giải cũng hơn trăm chars :joy: sao chênh lệch thế nhỉ

1 Like
long e, M=1e9+7, t, i,
p(int x, int y)
{
    return y ? e = p(x, y/2), y % 2 ? x * e%M * e%M : e * e%M : 1;
},
Simple_powers(int a, int b)
{
    a=p(a,b)+p(b,a);
    while(a%=M)
        t+=a%2*p(3,i++),
        a/=2;
    return t%M;
}

viết gộp vậy coi được ko? Nếu được thì giảm bớt được 3 ký tự :grin:

1 Like

Các thuật toán nhìn thì đơn giản
Nhưng để rút gọn là vấn đề
Trước tiên là cách khai báo - toán tử - xuất
Tham biến cần bao nhiêu là đủ
Có cần đề cập đến hàm không
Toán tử nào là ngắn nhất
Xuất gì ra???

2 Likes

Lỗi biên dịch :frowning:

1 Like

Bị TLE anh ạ :smile:

1 Like

C có thể bỏ khai báo trả về cho hàm, nó mặc định là int. Nên khai báo tất cả biến ở trên. Hàm simple pow không cần khai báo long nữa

1 Like

Em không hiểu?? :joy:

#define A (long a, int b) {
long r, y, t = 1, m = 1e9 + 7, p A
    return b ? p(a * a % m, b / 2) * (b & 1 ? a : 1) % m : 1;
}
int Simple_powers A
    for (y = p(a, b) + p(b, a); y %= m; y /= 2, t *= 3)
        r += y % 2 * t % m;
    return r % m;
}

:joy: Đúng là trình độ cao mà

5 Likes

define ăn gian kinh vãi :sweat:

3 Likes

Không biết cái này do kinh nghiệm hay sách vở nhỉ.
Chứ nhiều cái thật là không thể ngờ tới là nghĩ ra được. :sweat_smile:

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?