Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Các bạn giúp mình bài về số mũ trong C!!!

  1. #1
    Ngày gia nhập
    11 2011
    Bài viết
    3

    Wink Các bạn giúp mình bài về số mũ trong C!!!

    Đề bài thế này:
    Cho so tự nhiên A. Hãy tìm số tự nhiên N sao cho N lũy thừa N chia hết cho A, biết rằng 1<= A <=10^9

    bài này vừa đọc vào tưởng là dễ nhưng khi làm thì k đc vì tràn số

    Các bạn giúp mình với nhé.

    Thanks

  2. #2
    Ngày gia nhập
    11 2011
    Bài viết
    3

    không ai giúp mình được sao???

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    552

    N^N %A ==0 . Vậy sẽ có khả năng là N^k (k<=N) là đã %A ==0 rồi, ko cần đợi đến ^N
    Chứng minh dễ thôi: Do N^k chia hết cho A nên N^N= N^k * N^(N-k) cũng sẽ chia hết cho A.
    Giả sử A=8 , ta có dc số 2^3 %8 == 0 , nhưng mũ 3 vượt quá.
    Có số 4, thì chỉ cần 4^2=16 là đã %8 ==0 rồi, ko cần đợi đến 4^4
    Có số 6, 6^3 là đã %8==0 rồi, ko cần đợi đến 6^6.

    Tuy nhiên để tối ưu cái này cần phải đi sâu vào các con số và móc ra điều cốt lõi nữa.
    Có khả năng nào khi phân tích A thành các thừa số nguyên tố???. N muốn thỏa N^N(hay N^k ) chia hết A thì N cũng phải chia hết cho toàn bộ các thừa số nguyên tố đó ?? Nếu điều này đúng, ta sẽ ko cần tới vòng lặp lớn đến mức 10^9 . Ta chỉ việc đi tìm các thừa số nguyên tố của A, rồi tính Bội chung nhỏ nhất cho các thừa số nguyên tố đã phân tích (tức là nhân chúng lạ với nhau, bỏ các cơ số mũ >1) .
    Số mũ k sẽ là số mũ lớn nhất của các thừa số có trong A .

    Ví dụ A = 8 * 9 = 2^3 * 3^2= 72 . Vậy số N cần tìm là N=2*3=6 , k sẽ là =3 , 6^3= 216 . Sẽ chia hết cho A
    @@ Hiện tại mình chỉ nghĩ ra dc có vậy . Đang bận việc xíu nên chưa code để kiểm nghiệm được , bạn thử xem sao

    Miền trị 10^9 thì có nhiều kiểu dữ liệu có thể biểu diễn dc mà, sao lại tràn
    Đã được chỉnh sửa lần cuối bởi clchicken : 30-11-2011 lúc 12:11 AM.
    Um Mani Padme Hum...!!

  4. #4
    Ngày gia nhập
    11 2011
    Bài viết
    3

    Bạn có thể viết code cho mình đc k, mình chưa hiểu lắm
    Mình làm theo phương pháp chân phương là chạy từ n=2-->A, và kiểm tra xem n^n có chia hết cho A hay k, nhưng vấn đề là không tìm được một kiểu thích hợp cho n do tràn số. Bạn nào có cách giải quyết vấn đề này k??

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Bạn ko chịu đọc bài của mình rùi @@ Hix
    Đọc cái đó mà ko hiểu thì xem code cũng vậy thôi Ngôn ngữ tự nhiên mà chưa hiểu thì đến gì ngôn ngữ lập trình chài @@
    Code đây, đọc ko hiểu thì quay lại bài trên đọc
    Code này chỉ mới build theo ý tưởng và chỉ để cho chạy được. Còn tối ưu hơn nữa thì chưa bàn đến
    C++ Code:
    1. #include <iostream>
    2. using std::sqrt;
    3. using std::cin;
    4. using std::cout;
    5. void Analyse(unsigned long a,unsigned long result[][2],int &size){
    6. //Prime factors will be added into "result" array
    7.     size=0;
    8.     unsigned long limit=a;
    9.     for (unsigned long i=2;i<=limit;) // change to "i<=a" to get faster
    10.         if (a%i==0){
    11.             result[size++][0]=i;
    12.             int exponent_count;
    13.             for(exponent_count=0;a%i==0;exponent_count++)
    14.                 a=a/i;
    15.             result[size-1][1]=exponent_count;
    16.         }
    17.         else
    18.             i++;
    19. }
    20. unsigned long Calculate(unsigned long result[][2],int size,unsigned int &exponent){
    21.     unsigned long s=1;
    22.     exponent=0;
    23.     for(int i=0;i<size;i++){
    24.         s*=result[i][0];
    25.         if (result[i][1]>exponent)
    26.             exponent=result[i][1];
    27.     }
    28.     unsigned long s_image=s;
    29.     while (s<exponent){
    30.         s*=s_image;
    31.         --exponent;
    32.     }
    33.     return s;
    34. }
    35.  
    36. void main()
    37. {
    38.     unsigned long a,n,prime_factors[1000][2];
    39.     int size;
    40.     unsigned int m;
    41.     cout<<"\n Input number A : ";
    42.     cin>>a;
    43.     Analyse(a,prime_factors,size);
    44.     n=Calculate(prime_factors,size,m);
    45.     cout<<"\n N =:"<<n<<" Exponent=:"<<m;
    46.     cout<<"\n";
    47.     system("pause");
    48. }
    Đã được chỉnh sửa lần cuối bởi clchicken : 01-12-2011 lúc 11:25 PM.
    Um Mani Padme Hum...!!

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mặc định Các bạn giúp mình bài về số mũ trong C!!!

    Làm cách của mình sẽ ko có khi nào phải động đến N^N tới mức N~10^9 và tính ra cả N^N.
    Xui nhất là số A là số nguyên tố, thì N cũng sẽ chỉ = A. Ko việc gì phải đi tính A^A để rồi kết luận N(A) chia hết cho A cả
    Do đó sẽ ko lo bị tràn số ra khỏi miền trị của KDL.

    Trích dẫn Nguyên bản được gửi bởi nlhuykhang Xem bài viết
    Bạn có thể viết code cho mình đc k, mình chưa hiểu lắm
    Mình làm theo phương pháp chân phương là chạy từ n=2-->A, và kiểm tra xem n^n có chia hết cho A hay k, nhưng vấn đề là không tìm được một kiểu thích hợp cho n do tràn số. Bạn nào có cách giải quyết vấn đề này k??
    Cách này nguy hiểm ở chỗ n chỉ cần chạy đến 10 là 10^10 đã tràn ra khỏi miền trị rồi. Trong khi ta chả cần phải biết N^N = bao nhiêu cả .
    n mà chạy lên cỡ khoảng vài chục là mũ vài chục lên thì thấy có vẻ mệt mỏi cho cái máy rồi
    Hơn nữa Phép toán Mũ là 1 phép toán tiêu hao khá nhiều "kalo" của Vi xử lý đấy
    Đã được chỉnh sửa lần cuối bởi clchicken : 30-11-2011 lúc 12:06 AM.
    Um Mani Padme Hum...!!

  7. #7
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Sáng nay vừa ngẫm lại.
    Sửa cái chỗ này lại 1 tí là chương trình chạy có vẻ nhanh hơn nhiều
    C++ Code:
    1. void Analyse(unsigned long a,unsigned long result[][2],int &size){
    2. //Prime factors will be added into "result" array
    3.     size=0;
    4.     //unsigned long limit=a;
    5.     for (unsigned long i=2;i<=a;) // sửa i<= a;
    6.         if (a%i==0){
    7.             result[size++][0]=i;
    8.             int exponent_count;
    9.             for(exponent_count=0;a%i==0;exponent_count++)
    10.                 a=a/i;
    11.             result[size-1][1]=exponent_count;
    12.         }
    13.         else
    14.             i++;
    15. }
    Um Mani Padme Hum...!!

  8. #8
    Ngày gia nhập
    11 2011
    Bài viết
    32

    mình dùng thử excel kiểm tra, A=17( số nguyên tố) thì cho N = 14 thôi chứ k phải 17 như bạn chicken nói, k bit excel kiểm tra đúng k nữa

  9. #9
    Ngày gia nhập
    10 2011
    Bài viết
    552

    14 có mũ bao nhiêu cũng ko chia hết cho 17 dc . Bởi 14 bản thân nó ko mang trong mình các thừa số nguyên tố của 17.
    14= 2 * 7 cho nên có mũ bao nhiêu thì cũng chỉ là 2^N * 7^N, ko thể nào chia hết cho 17 dc.
    Cụ thể 14^14 = 1 cái số gì đấy rất bự nhưng /17 vẫn ko dc tròn
    Bạn check lại excel thử xem ?
    Đã được chỉnh sửa lần cuối bởi clchicken : 01-12-2011 lúc 11:18 PM.
    Um Mani Padme Hum...!!

  10. #10
    Ngày gia nhập
    11 2011
    Bài viết
    3

    Trích dẫn Nguyên bản được gửi bởi 5fox Xem bài viết
    mình dùng thử excel kiểm tra, A=17( số nguyên tố) thì cho N = 14 thôi chứ k phải 17 như bạn chicken nói, k bit excel kiểm tra đúng k nữa
    Nếu A là số nguyên tố thì kết quả chắc chắn là A mà bạn, có thể bạn sai ở đâu rồi

Các đề tài tương tự

  1. Hàm trong C Giúp đỡ về đọc FILE trong 1 folder riêng biệt trong lập trình C.
    Gửi bởi itus1994 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 29-12-2013, 09:04 PM
  2. Sự cố Nhờ mod chuyển giúp bài "Sắp xếp số thứ tự ngay trong bảng của 1 database?" từ MySQL sang MSSQL giúp!
    Gửi bởi hu-xeko trong diễn đàn Ý kiến, đề xuất và khiếu nại
    Trả lời: 1
    Bài viết cuối: 12-03-2012, 07:48 PM
  3. Bài tập C++ help giúp em sữa lỗi trong hàm tìm kiếm sách và gọi hàm trong chuơng trình quản lí sách
    Gửi bởi Mr.vu112 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 17-11-2011, 07:21 PM
  4. Bài tập C++ Giúp mình viết 1 đoạn code hoàn chỉnh trong C++ về random trong giới hạn
    Gửi bởi sai211dn trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 06-10-2011, 08:01 PM
  5. Hàm trong C++ không nằm trong main vẫn chạy đúng. Giải thích giúp?
    Gửi bởi tuvan1011 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 15
    Bài viết cuối: 02-09-2009, 12:58 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn