pow関数が上手く動作しない、setに謎の値が入ってしまう。

Question

X以下の最大のべき乗数を出力するプログラムを作りたい。

問題のリンク:Atcoder097B

制約

・1 <= x <= 1000
・ｘは整数
・べき乗数とは、ある1以上の整数bと2以上の整数pを使ってb^pとかける整数のことを指すこととします。

---

この問題を解くために以下のプログラムを実装しました。

#include<bits/stdc++.h>
using namespace std;
int main(){
  int x;
  cin>>x;
  set<int> s;

  //setに1000以下のべき乗数を全て用意
  for(int i=1;i<=31;i++){
    for(int j=2;j<=9;j++){
      int a=pow(i,j);
      if(1000<a) break;
      s.insert(a);
    }
  }

  //x以下の最大べき乗数を出力する
  auto itr = s.end();
    while (itr != s.begin()) {
      if(*itr<=x){ cout<<*itr; return 0; }
        itr--;
    }
}

しかし、実行結果が以下のようになってしまい、上手くいきません。
（入力が10の時は上手くいった。）
入力：1 -->　出力：何も出てこない
入力：999　-->　出力：41

そこでsetの中身を、スペースで区切って末尾のイテレータから出力すると、以下のような結果になりました。

41 1000 960 899 840 783 729 675 624 576 528 512 483 440 399 361 343 324 289 256 243 224 216 196 168 144 128 124 120
 99 81 64 49 36 32 27 24 16 9 8 4

ここで、以下の疑問点が浮かび上がりました。

・なぜ41という値が入っているのか？
・41がなぜ一番最初に出力されるのか？
・なぜ10^2や5^2の値がpow関数で正しく計算されていないのか？
・なぜ1^2や1^3の値がsetに入っていないのか？

これらの疑問点について、回答していただけると幸いです。

環境

ＯＳ：windows10
エディタ：ａｔｏｍ
コンパイラ：ＭｉｎＧＷ

Answer 1

itr.end()は最後の要素の次なので、

  auto itr = s.end();
  while(true){
    itr--;
    if(*itr<=x){ cout<<*itr; return 0; }
    if(itr == s.begin()) break;
  }

でしょうか。

・なぜ41という値が入っているのか？
・41がなぜ一番最初に出力されるのか？

*(s.end())は個数のようです。

・なぜ10^2や5^2の値がpow関数で正しく計算されていないのか？

powは指数関数や対数関数を使うので、正確に計算できません。
切り捨て前に、+0.5して四捨五入にしましょう。
あるいは、整数で掛け算のループをしてべき乗を求めるか。

・なぜ1^2や1^3の値がsetに入っていないのか？

setには入ってますが、*(s.begin())を見て無いから表示されてないだけです。

Comments

[subaru-k]

丁寧なご回答ありがとうございます。
おかげで疑問点が解決しました。

Answer 2

・なぜ41という値が入っているのか？
・41がなぜ一番最初に出力されるのか？
*s.end()は要素を指さないからです。s.end()の一つ前がsetの最後の要素です。
なので、while ループを回すならs.begin()から回す必要があります。

  auto itr = s.begin();
    while (itr != s.end()) {

・なぜ10^2や5^2の値がpow関数で正しく計算されていないのか？
浮動小数点数をそのままintにキャストすると、誤差が生じて正しい値になりません。
例えば、pow(10,2) = 99.99999... を int にキャストすると 99 になってしまいます。
なので、int a=pow(10,2) + 1e-7; として 100.00000... にするか。
最初から int で累乗を計算すると解決します。

・なぜ1^2や1^3の値がsetに入っていないのか？
これは、*s.begin()が1^2=1^3=1ですが、出力する前にbreakしているためです。

あと質問とは関係ないですが気になったこととして、
int a=pow(i,j);
で、pow(i,j)の値が最大31^9になっています。
31^9をintにキャストすると、intの値の範囲 2,147,483,647 を越えオーバーフローしてしまいます。

Comments

[subaru-k]

丁寧なご回答ありがとうございます。
おかげで疑問点が解決しました。