[Code ngắn nhất] SIMPLE_POWERS

[sample (<script>alert("hacked")</script>)]

Đề 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

[drgnz]

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ự

[sample (<script>alert("hacked")</script>)]

simple_powers return int là đc 176 ký tự

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 đó?

[drgnz]

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;
}

[sample (<script>alert("hacked")</script>)]

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

[drgnz]

nó là thế này

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

[sample (<script>alert("hacked")</script>)]

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

[drgnz]

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 .

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

[langtucdoc]

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

[Tung_BK (Tùng BK)]

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

[langtucdoc]

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 sao chênh lệch thế nhỉ

[tntxtnt]

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ự

[lo_vinh]

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???

[sample (<script>alert("hacked")</script>)]

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;
}

Lỗi biên dịch

[sample (<script>alert("hacked")</script>)]

Bị TLE anh ạ

[Gio (Gió)]

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

[sample (<script>alert("hacked")</script>)]

Em không hiểu??

[drgnz]

#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;
}

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

[tntxtnt]

define ăn gian kinh vãi

[drgnz]

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.