数字の最初と最後のk桁

Question

私は10^9という大きさの最初と最後のk桁を生成するためのC++コードを書いています。 （k < = 9）。このように私に出力を与える

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; 
} 

：入力として9及び3を与えられた場合 、それは電源9（TO 9の最初と最後の3桁を与える関数foo（）がある

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; 
    } 

9^9）すなわち387と489です。しかし、まだいくつかのテストケースがありません。 誰かが私のコードがうまくいかないテストケースを見つけるのを助けてくれますか？ 109≤

1≤nは、1≤K≤9 問題の記述：あなたのコードが正常に動作するようですhttp://www.codechef.com/problems/MARCHA4/

Answer 1

n^n <= 10^9あれば、その場合には。ただし、nのサイズが大きい場合は、11^11とし、最後の4桁の数字は0611としてください。コードは611と表示されます。基本的には、必要なときに先行ゼロを出力しません。

Answer 2

k = 9とする。今、m = 1e9、およびt <= 1e9 - 1です。 t * tは、1e18 - 2e9 + 1と同じくらい高くなる可能性があり、59.8ビットが必要です。

大丈夫ですが、63ビットの大きさ（および記号の1つ）を持つ64ビットのlong long intでは問題ありませんが、他の人が同じ分析を繰り返さないようにここに残します。

Answer 3

これは本当に質問には答えていませんが、それはほとんど簡単ですが、分かち合う価値があると思います。 「長いコメント」機能があったら、それを使っています。

編集：ただ、問題（あなたの代わりにSTRのはreprを使用する場合のみのものはLを扱っている）されていないその

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

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

自身のオーバーフローのLを排除する代わりのreprのSTRを使用して気づきました

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

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

どちらもリードしているゼロ

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

これは、モジュラーリットルを言うかされていません私はあなたが全体の数字を生成せずにこれをどうやってやったかについて読書が本当に好きでした。私はOPの質問を読むまでmodfについて全く知らなかったし、fooのボディはとても興味深い。

Answer 4

nは正の整数であると言われていますか？たとえば、(-8)^(-8)は10進数で完全に表現可能ですが、プログラムで処理できません。

Answer 5

問題は浮動小数点を使用していると思います。数字の最初の桁を見つけるには、実際には完全な精度が必要です。

残念ながら、コンテスト審査員は明らかに "有効桁数"！= "正しい桁数"を理解していません。

はおそらく正確に計算するためのいくつかの巧妙な方法が存在する（N * Nを、N = 10 * 9）メモリを排気するが、非常に良好な推定値の最初の桁を求めることなく、単に最初の数字を見つけると同じではありません答えの