Giải pháp tính a^b mod n?

#1

Mọi người có thể chỉ ra lỗi sai trong đoạn code này của mình được không, không hiểu sao, mình nộp bài mà không qua hết các test:

Đề bài là tính a^b mod 10e9+7

#include <stdio.h>
const int M = 1000000007;
int b1[1000];
int size;
// ham nay chi la convert 1 so tu he 10 sang he 2, sau do minh luu vao mang b1 thoi
void convert_decima_binary(int n) {
    int b2[1000];
    int i = 0;
    while(n > 0) {
        b2[i] = n%2;
        n = n/2;
        i++;
    }
    int m = i - 1;
    size = i - 1;
    for( ; m >= 0 ; m--) {
        b1[i - m - 1] = b2[m];
    }
}
// đây là hàm chính của mình
int mod_exponent(int base, int exp) {
        convert_decima_binary(exp);
        int x = base;
        int y = (b1[size] == 1 )? base : 1;
        for(int  i = size - 1 ; i >= 0 ; i--) {
            x = (x*x)%M;
            if(b1[i] == 1)
                y = ( y == 1) ? x : (y*x)%M;
        }
        return y;
}
int main() {

    int a,b;
	scanf("%d %d",&a, &b);
	int tmp = mod_exponent(a,b);
	if (tmp < 0)
           printf("%d", tmp + M);
        else
           printf("%d", tmp);
	return 0;
}
#2

Bạn nên tìm hiểu về định lý Fermat nhỏ để giảm thời gian tính toán và bộ nhớ để lưu chữ biến kết quả.
Chỗ biến a,b để kiểu long long mới pass nhé bạn (long long khoảng 10^18 gì đó, còn int có 10^9 bé quá )

4 Likes
#3

Có thể bỏ bước đổi ra nhị phân :slight_smile: ta tính được a^1, a^2, a^4, a^8… rồi nhân vào theo biểu diễn nhị phân của b như bạn đã làm.

4 Likes
#4

đúng vậy bạn ơi. tks bạn, mình đang thử

#5

Tại mình nghĩ cái phần đổi ra đấy chỉ có 0(logn) khá nhỏ nên việc loại bỏ nó đi là không cần thiết và hơn nữa, nếu bỏ đi mình cũng khó có thể implement được thuật toán để tính các a mũ (2 mũ i)

#6

Mình cũng chưa hiểu đề bài nữa nên không biết sao giúp bạn luôn ^.^

#7

Đọc định lý femat nhỏ khó hiểu quá, bạn có thể giúp mình được không?

#8

không sao đau cám ơn bạn.

#9

Cho bạn nè. :slight_smile:

https://vnoi.info/wiki/translate/he/Number-Theory-3

P/s: Nếu thích dùng đồ của nhà thì cũng có luôn. :slight_smile:

3 Likes
#10

Hi, mình đoán size là tổng số bit phải không?
Nếu đúng vậy, thì bạn không nên đặt size là vị trí (index) cuối cùng của mảng.
Sau khi chương trình thực hiện hàm convert_decima_binary thì size = size - 1, với trường hợp n <= 0 thì xảy ra lỗi out of range (size < 0).

4 Likes
#11

Cám ơn bạn một bug khá hay mà mình không để ý. Bạn có thể gợi ý cho mình cách giải quyết không, với trường hợp bài này thì khi b âm mà a dương thì sẽ được một thập phân, nhỏ, có thể tiến tới 0. Theo mình biết kết quả của mod thường là số nguyên.

#12

Cám ơn bạn về cơ bản thì link bạn gửi đó với cách mình implement thì là 1.

Ai cần có thể đọc thêm ở đây: http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/fastexp.pdf

#14

Nhân tiện bạn nào hiểu được định lý femat nhỏ có thể giải thích cho mình bằng vì dụ được không.

Còn về bài trên thì mình chỉ cần thay đổi kiểu int thành long long là AC rồi.

1 Like
#15

Dễ hiểu nhất là ntn :slight_smile:

Xét các chuỗi gồm 7 hạt, mỗi hạt có thể là màu đỏ, lam hoặc trắng. Có 3^7 chuỗi như vậy :slight_smile:

Giờ ta kết chuỗi lại thành vòng, thì hai chuỗi là tương đương khi và chỉ khi kết lại thành vòng giống nhau. Ví dụ:

  1. RBWBRWW
  2. WWRBWBR

Gom hết chuỗi tương đương thành cụm (do tính chất bắc cầu :smiley: ) thì mỗi cụm đều có 7 chuỗi hạt, trừ chuỗi toàn đỏ, toàn lam và toàn trắng là 3 cụm mỗi cụm đúng 1 chuỗi. Vậy 3^7 - 3 chia hết cho 7, hay 3^7 = 3 (mod 7).

3 Likes
#16

ko cần đổi thành long long nè: :V :V

#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>

template <class T, class ModFunction>
T calmod(T a, T b, T m, T init, ModFunction&& f)
{
    for (; a; a >>= 1, b = f(b, b, m))
        if (a & 1)
            init = f(init, b, m);
    return init;
}

// Calculate a*b (mod m)
uint32_t mulmod(uint32_t a, uint32_t b, uint32_t m)
{
    if (b < a)
        std::swap(a, b); // so b is the bigger number
    if (b >= m)
    {
        if (m > std::numeric_limits<uint32_t>::max() / 2u)
            b -= m; // avoid 1 modulus
        else
            b %= m;
    }
    return calmod(a, b, m, 0u, [](uint32_t a, uint32_t b, uint32_t m) {
        if (a >= m - b) // equivalent to (a + b) >= m
            a -= m;
        return a + b;
    });
}

// Calculate a^b (mod m)
uint32_t powmod(uint32_t a, uint32_t b, uint32_t m)
{
    return calmod(b, a, m, 1u, mulmod);
}

int main()
{
    assert(powmod(13, 10, 1024) == 457);
    assert(powmod(666666, 1234, 987654) == 374178);
    assert(powmod(4000000001, 4000000007, 3000000007) == 705496200u);
    assert(powmod(4000000001, 4000000007, 300007) == 238321u);
}

chôm từ https://stackoverflow.com/a/18680280 về chế biến lại :horse:

2 Likes
#18

Gán size = i là được.
Còn trường hợp b âm còn được gọi là inverse mod.
Bạn có thể tham khảo: https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
Có 1 điều mình khó hiểu là: inverse mod giải được khi a hay b hay n (mod n) phải là số nguyên tố. Rõ hơn như nào thì mình chịu.

#19

Không phải, điều kiện là n với a nguyên tố cùng nhau :smiley:

4 Likes
#20

Xin lỗi mọi người nhiều, máy tính mới bị tại nạn chưa về, mấy ngày nay không làm ăn được gì cả. Nên chưa đọc hết comment của anh em được.

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