первая и последняя k цифр номера n ^ n

Question

Я написал код на C ++ для генерации первой и последней k цифр числа размером 10 ^ 9. (К <= 9). </p>

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

где функция foo ():

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 в качестве входных данных, это дает первые и последние 3 цифры 9 степени 9 (9 ^ 9), то есть 387 и 489. Но я все еще пропускаю некоторые тестовые случаи. Может ли кто-нибудь помочь мне найти контрольный пример, для которого мой код не будет работать?

1 ≤ n ≤ 109, 1 ≤ k ≤ 9 постановка задачи: http://www.codechef.com/problems/MARCHA4/

Answer 1

Если n^n <= 10^9, то в этом случае ваш код работает нормально. Однако, если вы допустите большее значение n, скажем 11^11 и запросите последние 4 цифры этого значения, которые равны 0611, ваш код будет печатать только 611 По сути, он не печатает начальные нули, когда должен.

Answer 2

Это на самом деле не отвечает на вопрос, и это почти тривиально легко, но я думаю, что стоит поделиться. Если бы была возможность «длинных комментариев», я бы использовал ее.

РЕДАКТИРОВАТЬ: только что заметил, что использование 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')

Это не значит, что модульные журналы и прочее не очень крутые - напротив, мне очень понравилось читать о том, как вы это делали, не генерируя всего числа. Я ничего не знал о modf, пока не прочитал вопрос OP, и тело foo очень интересно.

Answer 3

Я думаю, что проблема заключается в использовании плавающей запятой. Нахождение первой цифры числа на самом деле требует идеальной точности.

К сожалению, судья конкурса, очевидно, не понимает, что «количество значащих цифр»! = «Количество правильных цифр».

Возможно, есть какой-то умный способ точно вычислить (n * n, n = 10 * 9) без исчерпания памяти, но поиск первых цифр очень хорошей оценки просто не совпадает с поиском первые цифры ответа.

Answer 4

Вам сказали, что n - это положительное целое число?Например, (-8)^(-8) прекрасно выражается в десятичном формате, но ваша программа не может его обработать.

Answer 5

Предположим, что k = 9.Теперь m = 1e9 и t <= 1e9 - 1.t * t тогда может достигать 1e18 - 2e9 + 1, что требует ... 59,8 бит.

Хорошо, не проблема с 64-битным long long int, который имеет величину 63 бит (и 1знака), но я оставлю это здесь, чтобы другие не повторяли тот же анализ.