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

[09520144]

sr mọi người! cái công thức a%b = (a^b)%c là bị sai rồi. mới chứng minh lại thấy bị sai

[10520355]

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

khi b=1 và c =1 thì bc = c ( chứ không phải bc>c) vậy bc - c =0 ==> a^(b*c) chia hết cho a^c .Còn ở post #21 của anh, anh cho bc luôn > c mà quên mất trường hợp đó. vì vậy với điều kiện của bài toán thì bc >= c thì mới đúng. có vậy thôi mà.

[10520355]

còn ở bài toán này mình xin ra 3 code đều chạy với giới hạn từ 1 đến 2 tỉ với thời gian < 1s.

Code 1: là cách của bạn Nguyễn Phi Hùng đã có chỉnh sửa để đúng với giới hạn bài toán

#include <iostream>
using namespace std;
long a, b, c;

long long xuly2(long long a,long b,long c)
{
    long long d=1;
    while(b>0)
    {
        while (b%2==0)
        {
            a=(a*a)%c;
            b=b/2;
        }
        d=(d*a)%c;
        b--;
    }
    return d;
}
int main()
{
    cin>>a>>b>>c;
    cout<<xuly2(a,b,c);
    return 0;
}

Code 2 viết theo cách đệ quy với thuật toán giống như bạn quoctinvn đã trình bày

#include <iostream>
using namespace std;
long a, b, c;
long long dequy(long a, long b, long c)
{
    if(b==0) return 1%c;
    if(b %2 ==0) 
    {
        long long t=dequy(a, b/2, c);
        return (t*t)%c;
    }
    else
    {
        long long t=dequy(a, b/2, c);
        t=(t*t)%c;
        return (t*a)%c;
    }
}

int main()
{
    cin>>a>>b>>c;    
    cout<<dequy(a,b,c);
    return 0;
}

Code 3: code này hơi khó hiểu, mà mỉnh cũng không biết trình bày thế nào để các bạn hiểu nữa. :funny: Nhưng mà cũng đưa code ra để các bạn xem.

#include <iostream>
using namespace std;
long a, b, c;

long long xuly(long a, long b, long c)
{
    long long tich=a%c, ans = 1%c;
    while(b>0)
    {
        if(b&1==1) ans=(ans*tich)%c; // b la so le
        b>>=1; tich=(tich*tich)%c;
    }
    return ans;
}

int main()
{
    cin>>a>>b>>c;    
    cout<<xuly(a,b,c);
    return 0;
}

[11520132]

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

Sao lại lũy thừa bao nhiêu lần chia dư cũng ra x được anh. ví dụ 5 mod 3 =2, 5^2 mod 3 = 1

[11520447]

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

chưa hiểu lắm chỗ này, c(b-1) là số thập phân thì a^c(b-1) đâu fai số nguyên :-s
ko bik mình hiểu đúng ko :-s

[10520355]

chưa hiểu lắm chỗ này, c(b-1) là số thập phân thì a^c(b-1) đâu fai số nguyên :-s
ko bik mình hiểu đúng ko :-s

c, b xét ở bài toán này là số nguyên mà, đâu có xét số thập phân j đâu.:happy: