[Lập trình newbie] Mỗi ngày một bài toán (số10)

[quoctinvn]

Em thấy
(a^b)%c = ((a^(b/2))%c * (a^(b/2))%c * a) % c nếu b/2 không nguyên. b/2 nguyên thì không * a. Kiểu chia nhị phân, độ phức tạp log :salute:
bài mở rộng thì em no comment :sweat:

[11520132]

nếu ở trường hợp b=0, c=1 thì bạn sai đấy. còn ở những nơi có lũy thừa mà bạn sử dụng kiểu int thì bị lỗi là cái chắc rồi. nếu để kiểu int thì bạn chỉ chạy đúng với số có 5 chữ số thôi.

thì if c==1 thì return 0 .
Còn cái sau chắc nới sang long int hay long long int chắc được.

[09520500]

#include <stdio.h>
int xuly(int a,int b,int c)
{
    int d=1;
    while(b>0)
    {
        while (b%2==0)
        {
            a=(a*a)%c;
            b=b/2;
        }
        d=(d*a)%c;
        b--;
    }
    return d;
}
void main()
{
    int a;
    int b,c;
    scanf("%d%d%d",&a,&b,&c);
    printf("%d",xuly(a,b,c));
} 

thuật toán thì có cái công thức ở post số 2
Ai giải thích cho em tại sao với số lớn thì nó lại ra kết quả sai không ?
Có phải cái chỗ a*a thì cỡ 1 tỉ x 1 tỉ 20 chữ số nên vượt qua giới hạn int không ?

Chính xác là tràn số int đó em :beatbrick:

[09520144]

xin lỗi nha! mình có một chút ý kiến là tại sao bài toán này phải làm cho rắc rối vì nếu: giả sử a%c= x thì dù có lũy thừa bao nhiêu lần cũng chia dư được x thôi vậy sao các bạn không biến bài toán thành một bài toán chia dư của a và c không phụ thuộc mũ b nữa. vì điều kiện chỉ từ 1 đến 1 tỉ nên viết một hàm chia dư của 2 số chạy dưới 1s cũng không khó. mình tin mọi người viết được. còn nếu ai có thắc mắc cứ liên hệ qua mail mình sẽ giải thích kĩ hơn thanhlam24101991@gmail.com. thanks

[09520144]

còn bài toán mở rộng chắc chắn lúc nào output cũng bằng 0 rồi! không cần bàn nữa

[09520144]

sao không chứng minh đơn giản hơn là ((a^b)^c)%(a^c)= (a^(b*c))%(a^c) mà b.c>c => ((a^b)^c) luôn chia hết cho (a^c). done!^^

[09520144]

còn bài (a^b)%c thì hồi đó nhớ đi học phổ thông các bạn đã được chứng minh là luôn bằng a%c rồi. test lại kiến thức toán bằng cách chứng minh lại tính chất đó xem nha các cá bơ^^

[11520233]

xin lỗi nha! mình có một chút ý kiến là tại sao bài toán này phải làm cho rắc rối vì nếu: giả sử a%c= x thì dù có lũy thừa bao nhiêu lần cũng chia dư được x thôi vậy sao các bạn không biến bài toán thành một bài toán chia dư của a và c không phụ thuộc mũ b nữa. vì điều kiện chỉ từ 1 đến 1 tỉ nên viết một hàm chia dư của 2 số chạy dưới 1s cũng không khó. mình tin mọi người viết được. còn nếu ai có thắc mắc cứ liên hệ qua mail mình sẽ giải thích kĩ hơn thanhlam24101991@gmail.com. thanks

trước giờ chưa thấy a^b %c = a % c mà chỉ thấy a^b % c = ((a%c)^b)%c thôi.
test cụ thể: a= 2, b=2, c=3
a^b %c = 2² % 3 = 4 %3 = 1
a%c= 2%3 = 2
((a%c)^b)%c= ((2%3)²)%3 = (2²) % 3 =1

không biết anh chứng minh công thức a^b %c = a % c như thế nào đây.

[11520233]

sao không chứng minh đơn giản hơn là ((a^b)^c)%(a^c)= (a^(b*c))%(a^c) mà b.c>c => ((a^b)^c) luôn chia hết cho (a^c). done!^^

với a, b, c >=1 thì b.c>=c. cần kết hợp với điều kiện thì đáp án mới đúng.

[11520233]

còn bài (a^b)%c thì hồi đó nhớ đi học phổ thông các bạn đã được chứng minh là luôn bằng a%c rồi. test lại kiến thức toán bằng cách chứng minh lại tính chất đó xem nha các cá bơ^^

anh có thể đưa bài chứng minh đẳng thức trên được không?

[quoctinvn]

lúc em học đội tuyển, có thầy ở đh sư phạm dạy cách (a^b)%c bằng cách chia 2 như trên, chưa học và cũng chưa có ai dạy (a^b)%c = a%c :surrender:
em nghĩ trường hợp đó chỉ đúng khi a >= c thôi :sweat: còn tổng quát thì cách như trên :salute:

[09520144]

về trường hợp mở rộng bạn My chịu khó xem lại điều kiện đề bài nha. tại vì anh ra đề này đã cho điều kiện là 1 đến 1 tỉ rồi đó.

[09520144]

còn đối với công thức giải bài cơ bản. anh sẽ chuyển câu trả lời lên. giờ đang chưa có thời gian để làm lại tối sẽ chứng minh rồi chuyển lên cho mọi người
còn về trường hợp bạn nói thì đúng là có một ngoại lệ là khi chia nếu a nhỏ hơn c thì sẽ luôn có số dư là a. nhưng ở đây các bạn có thể check điều kiện if cho ngoại lệ này chẳng hạn nếu b đủ lớn để có thể làm cho a^b lớn hơn thì chúng ta sẽ coi a là một lũy thừa vừa đủ để lớn hơn c sau đó chia lấy dư rồi suất đáp án. còn nếu b không đủ làm cho a^b lớn hơn c thì các bạn chuyển bài toán về tính bài toán tính lũy thừa a^b cách này sẽ nhanh hơn vì thuật toán tính bài toán a^b vẫn có độ phức tạp nhỏ nhất là hàm log vẫn sẽ cho ra kết quả dưới 1s

[10520355]

về trường hợp mở rộng bạn My chịu khó xem lại điều kiện đề bài nha. tại vì anh ra đề này đã cho điều kiện là 1 đến 1 tỉ rồi đó.

b=1, c=1 thì làm sao mà bc > c được.

[09520144]

vậy chứ vậy chứ a^(b*c)không chia hết cho a^c nếu b=1 c=1 sao? cả 2 vế đều là a mà?