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

[09520281]

Hi all. Với bài toán "tìm huyết thống" ở bài trước chắc các bạn cũng hiểu được phần nào quan hệ huyết thống ở trong trường ta :aboom:. Hum nay là cũng là một bài toán số học:
Bài toán:
Cho a, b, c <= 1 tỉ. Tính (a ^ b) % c. (Phép ^ chỉ phép lũy thừa)
Time limit: 1s
Memory: 5MB
Ví dụ:
Input:
2 3 2
Out put:
0

Mở rộng bài toán khó hơn: [(a^b)^c]%(a^c). :shock:
Have fun :sexy:.

[11520132]

Vừa mới nhắc bên thread bên kia thì bên này có rồi :love:. Bài này có tìm được tình yêu không anh Mr.Kiều
Có được dùng thư viện math.h không nhỉ
nhớ không nhầm thì (a^b)%c=((a%c)^b)%c Giờ thì thấy đơn giản hơn rồi

[10520355]

giới hạn dưới của a, b, c ở bài toán mở rộng là bao nhiêu vậy anh.

[09520281]

giới hạn dưới của a, b, c ở bài toán mở rộng là bao nhiêu vậy anh.

thử làm với điều kiện như trên luôn xem sao

[10520355]

vậy giới hạn bắt đầu từ 1 đến 1 tỉ phải không anh

thử làm với điều kiện như trên luôn xem sao

[09520281]

vậy giới hạn bắt đầu từ 1 đến 1 tỉ phải không anh

uh :funny:

[09520500]

Ca này hơi căng thẳng đấy! :misdoubt:
Anh em code tìm ra bí mật của bài toán tìm người yêu này nào :go:

[10520355]

bài toán trên thì mình đã có cách giải. chỉ nói về bài toán mở rộng thôi.
ta có
(a^b)^c / a^c
= a^bc / a^c
= a^c(b-1)
Nếu a^c(b-1) là số nguyên thì ((a^b)^c % a^c) = 0
ngược lại nếu là số thập phân thì ((a^b)^c % a^c) khác 0

- Nếu c(b-1) >=0 thì a^c(b-1) sẽ là một số nguyên
mà với điều kiện a , b, c >=1 thì c(b-1) >=0
vậy a^c(b-1) sẽ luôn là số nguyên vậy ((a^b)^c % a^c) luôn = 0.

[09520500]

bài toán trên thì mình đã có cách giải. chỉ nói về bài toán mở rộng thôi.
ta có
(a^b)^c / a^c
= a^bc / a^c
= a^c(b-1)
Nếu a^c(b-1) là số nguyên thì ((a^b)^c % a^c) = 0
ngược lại nếu là số thập phân thì ((a^b)^c % a^c) khác 0

- Nếu c(b-1) >=0 thì a^c(b-1) sẽ là một số nguyên
mà với điều kiện a , b, c >=1 thì c(b-1) >=0
vậy a^c(b-1) sẽ luôn là số nguyên vậy ((a^b)^c % a^c) luôn = 0.

Hay đấy :sogood:

[11520132]

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

[09520668]

Ta có: (a^b)^c = (a^c)^b => [(a^b)^c] \ (a^c) = a^b và [(a^b)^c] % (a^c) = 0

[11520132]

à còn cái mở rộng thì (a^b)^c=a^bc=(a^c)^b
>> ((a^b)^c)%(a^c)=((a^c)^b)%a^c=0

[11520132]

Ta có: (a^b)^c = (a^c)^b => [(a^b)^c] \ (a^c) = a^b và [(a^b)^c] % (a^c) = 0

Ọc nhanh hơn mình

[10520355]

hic. a^cb / a^c = a^b
không biết công thức nào đây

Ta có: (a^b)^c = (a^c)^b => [(a^b)^c] \ (a^c) = a^b và [(a^b)^c] % (a^c) = 0

[10520355]

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

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.