chữ k đầu tiên và cuối cùng của số n^n

Question

tôi đã viết mã C++ để tạo số k đầu tiên và cuối cùng của một số lớn đến 10^9. (k < = 9).

cin>>n>>k; 
    cout << (unsigned long)floor(pow(10.0, modf(n*log10((double)n), &dummy) + k - 1)) << " "; // code that prints the first k digits 
    long long int ans = foo(n,k); // function that prints the last k digits 
    if(ans==0) 
    { 
    for(int i=0;i<k;i++) cout << "0"; 
    } 
    else{ 
      stringstream ss; 
      string s; 
      ss<<ans; 
      ss>>s; 
      if(s.size()!=k) 
      { 
       for(int i=0;i<(k-s.size());i++) 
      s="0"+s; 
      } 
      cout<<s; 
    } 

nơi function foo() là:

long long int foo(int n, int k) // code of the function 
{ 
    long long int m=1; 
    for(; k > 0; k--) m*=10; 

    long long int r=1, t=n % m; 
    while(n) 
    { 
    if (n % 2) 
     r = r * t % m; 
    t = t * t % m; 
    n >>= 1; 
    } 

    return r; 
} 

này mang lại cho tôi đầu ra như: nếu được 9 và 3 như đầu vào, nó mang lại cho đầu tiên và cuối cùng 3 chữ số 9 với sức mạnh 9 (9^9) tức là 387 và 489. Nhưng tôi vẫn bỏ lỡ một số trường hợp thử nghiệm. Bất cứ ai có thể vui lòng giúp tôi tìm ra trường hợp thử nghiệm mà mã của tôi sẽ không hoạt động?

1 ≤ n ≤ 109, 1 ≤ k ≤ 9 báo cáo vấn đề: http://www.codechef.com/problems/MARCHA4/

Answer 1

Nếu n^n <= 10^9, trong trường hợp này mã của bạn dường như làm việc tốt. Tuy nhiên, nếu bạn cho phép lớn hơn n, hãy nói 11^11 và yêu cầu 4 chữ số cuối cùng của số đó là 0611, mã của bạn sẽ chỉ in 611. Về cơ bản, nó không in bất kỳ số 0 hàng đầu nào khi cần.

Answer 2

Giả sử rằng k = 9. Hiện tại, m = 1e9 và t <= 1e9 - 1. t * t sau đó có thể cao tới 1e18 - 2e9 + 1, cần ... 59,8 bit. Ok, không phải là vấn đề với một bit 64 bit long long int, có 63 bit độ lớn (và 1 dấu), nhưng tôi sẽ để nó ở đây để những người khác không lặp lại cùng một phân tích.

Answer 3

Điều này không thực sự trả lời câu hỏi và dễ gần như dễ dàng, nhưng tôi cho rằng nó có thể đáng để chia sẻ. Nếu có một khả năng "bình luận dài" tôi sẽ sử dụng nó.

EDIT: chỉ cần chú ý sử dụng str thay vì repr sẽ loại bỏ L tự

def firstAndLastDig(k, num): 
    s = str(num) 
    return (s[:k], s[-k:]) 

def firstAndLastDigSelfExp(k,n): 
    return firstAndLastDig(k,n**n) 

tràn của nó không phải là một vấn đề (điều duy nhất là đối phó với các L nếu bạn sử dụng repr thay vì str),

firstAndLastDigSelfExp(6,12) 
('891610', '448256') 

firstAndLastDigSelfExp(42,491) 
('209417336844579728122309696211520194012462', '160453713040914743773217804810667483135091') 

Và không phải đang dẫn đầu zero

>>> firstAndLastDigSelfExp(4,9) 
('3874', '0489') 

này không làm nói l mô-đun ogs và các công cụ không phải là mát mẻ - trái lại tôi thực sự thích đọc về cách bạn đã làm điều này mà không tạo ra toàn bộ số. Tôi không biết về modf ở tất cả cho đến khi đọc câu hỏi của OP và cơ thể của foo là rất thú vị.

Answer 4

Bạn có biết rằng n là số nguyên dương không? Ví dụ: (-8)^(-8) hoàn toàn rõ ràng trong thập phân nhưng chương trình của bạn không thể xử lý.

Answer 5

Tôi nghĩ rằng sự cố đang sử dụng dấu phẩy động. Tìm chữ số đầu tiên của một số thực sự đòi hỏi độ chính xác hoàn hảo.

Thật không may, thẩm phán cuộc thi rõ ràng không hiểu rằng "số chữ số có nghĩa"! = "Số chữ số chính xác".

Có lẽ có một số cách thông minh để tính toán chính xác (n * n, n = 10 * 9) mà không làm cạn kiệt bộ nhớ, nhưng việc tìm các chữ số đầu tiên của ước tính rất đơn giản là không giống như tìm chữ số đầu tiên của câu trả lời.