LoginSignup
keith_campbell
@keith_campbell

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

ARC 106 A問題 "106" C++ 実装について

Q&A

Closed

C++AtCoder競プロ指数計算

解決したいこと

以下のようなプログラムで提出したところ、インプットN=359414837200037396でWAとなってしまいます。
自作で指数を計算する関数powintを与えてやったのですが、なぜこのようなことが起きるのか理解できません。

image.png

発生している問題・エラー

答えは-1とならなければなりませんが、1 28とでます。

解決策

既存のライブラリpowでは桁落ちするのは理解していたので、以下のlong doubleを返却するpowlにすれば解決します。

A.cpp
#include <bits/stdc++.h>
#include <unistd.h>
using lli = long long int;
using namespace std;
#define Rep(i, n) for(int i = 0; i < (int)n; i++)
#define Repi(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define Repv(i, vec) for(int i : vec)
#define Sort(vec) sort(vec.begin(), vec.end())
template<typename _T> void Out(_T x) { cout << x << endl; }
template<typename _T> void PrintVec(vector<_T> vec) {
    Rep(i, vec.size()) { cout << vec[i] << " "; }
    cout << endl;
}
template<typename _T> int Minval(_T vec) {
    return *min_element(vec.begin(), vec.end());
}
template<typename _T> int Maxval(_T vec) {
    return *max_element(vec.begin(), vec.end());
}
template<typename _T> int Sumvec(_T vec) {
    int sum=0; Repv(i, vec) sum+=i; return sum;
}
#define MAXV 50

long long intpow(long long base, long long a){
    long long ans = 1;
    while(a>0){ans*=base; a--;}
    return ans;
}

void _main() {
    // Input
    long long N;
    cin >> N;

    Repi(A, 1, MAXV){
        Repi(B, 1, MAXV){
            long long powval = powl(3,A) + powl(5,B);
            //pause();
            //cout << A << " " << B << " " << powval << endl;
            if(powval==N){cout << A << " " << B << endl; return;}
        }
    }
    Out(-1);
}


int main() {
    _main();
    return 0;
}
0

2Answer

yoshi389111
@yoshi389111

long long （64bit）でもオーバーフローが起きてしまったのだと思います。

Python で計算してみますが

>>> hex((3 ** 1) + (5 ** 28))
'0x204fce5e3e2502614'
>>> hex(359414837200037396)
'0x4fce5e3e2502614'

4桁ごとに区切ってみれば計算結果は 0x0002_04fc_e5e3_e250_2614 66bit 分の値になっています。

一方、N の方は 0x04fc_e5e3_e250_2614 となり、計算結果の下64bitと同じになっています。

1Like

Comments

  1. @keith_campbell

    Questioner

    調べていただき誠にありがとうございます！
shohirose
@shohirose

$3^A$と$5^B$およびその和がオーバーフローしないように計算しないといけないのですが、intpow(3,A)およびintpow(5,B)の部分でオーバーフローを考慮していません。正しくは下記のようにプログラムを書きます。

#include <iostream>
#include <vector>
#include <cstdint>
#include <utility>

using std::int64_t;

// N未満のべき乗を全て計算して返す関数
// v[n] == {base}^n
//
// 3Nおよび5Nはint64_tの範囲に収まるため、ループ内一時変数のtmpは
// オーバーフローしないことが保障される。
std::vector<int64_t> calcPows(int64_t base, int64_t maxExponent,
                              int64_t maxValue) {
  std::vector<int64_t> v;
  v.reserve(maxExponent + 1);
  v.resize(1);
  v[0] = 1;
  for (int64_t i = 1; i <= maxExponent; ++i) {
    const int64_t tmp = v[i - 1] * base;
    if (tmp >= maxValue) break;
    v.push_back(tmp);
  }
  return v;
}

// 3^A + 5^B = Nを満たすAとBを探して返す関数
// 見つからなければA=B=0を返す。
std::pair<size_t, size_t> findExponents(const std::vector<int64_t>& v3,
                                        const std::vector<int64_t>& v5,
                                        int64_t N) {
  for (size_t i = 1; i < v3.size(); ++i) {
    // 3^A < Nを満たす3^Aのみ含むので、0 < rsd < Nとなり
    // オーバーフローしないことが保障される
    const auto rsd = N - v3[i];
    for (size_t j = 1; j < v5.size(); ++j) {
      if (rsd == v5[j]) {
        return {i, j};
      } else if (rsd < v5[j]) {
        break;
      }
    }
  }
  return {0, 0};
}

int main() {
  int64_t N;
  std::cin >> N;

  const auto v3 = calcPows(3, 50, N);
  const auto v5 = calcPows(5, 50, N);
  const auto [A, B] = findExponents(v3, v5, N);

  if (A != 0) {
    std::cout << A << ' ' << B << std::endl;
  } else {
    std::cout << -1 << std::endl;
  }
}
1Like

Comments

  1. @keith_campbell

    Questioner

    コードまで載せていただき誠にありがとうございます！
    `long long`でも取り扱えていなかったことには気づけませんでした。

Your answer might help someone💌

LoginSign Up