質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

728閲覧

あるNに対してa^b(a,b≧2)と表せないようなN以下の数 / sympy.factorint()を用いた場合

kay_ventris4

総合スコア269

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/03/23 04:14

編集2021/03/23 04:17

#問題
イメージ説明
AtCoder Beginner Contest 193 / C問題より

#試した手法
AtCoderでは、どうやらsympyライブラリは使えないようですが、パッと思いついたのでこれを用いて問題解決を図ります。
1~Nの数iに対し、それぞれをsympy.factorint(i).keys()及び.values()を行うことでaとbのリストをそれぞれ生成します。また、辞書の長さlに対し、lが2以上の場合は、bの要素が全て一致し、かつそれらが全て2以上であった場合、そのような数はa^bの形で表せると考えました。またlが1の時は、bがシンプルに2以上であればそのような数はa^bの形で表せると考えました。そしてこれらを逐一カウントし、最後にNから引いた数が問題の答えだという要領です。

以上の考察に従って書いたのが下のコードです:

Python

1from sympy import factorint 2 3N = int(input()) 4 5cnt = 0 6 7for i in range(0, N + 1): 8 9 a = list(factorint(i).keys()) 10 b = list(factorint(i).values()) 11 l = len(factorint(i)) 12 13 if l > 1: 14 if all(el >= 2 for el in b) == True and len(list(set(b))) == 1: 15 cnt += 1 16 17 elif l == 1: 18 if all(el >=2 for el in b) == True: 19 cnt += 1 20 21print(N - cnt)

#質問
sympyがAtCoderの指定ライブラリでない以上、採点の手段がないのですが、例として数例の問いと答えが上がっていたのでそれらを試したところ、例えばN=8では6が正しく出力されたのですが、N=100000では本来99634が出力されるはずだったのですが、何故か出力されたのは99743とだいぶずれた数値でした。見落としの可能な限りないように細心の注意を払って構築したのですが、どのような箇所に誤りがあると考えられますでしょうか。幾分雑な形の質問とはなってしまいましたが、お力添え頂ける箇所がございましたら、何卒ご教授のほどよろしくお願い申し上げます。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

144は2^4*3^2なのでbの要素は一致しませんが、12^2という形で表せます。

投稿2021/03/23 04:36

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2021/03/23 04:42

あっ… 実験が甘かったです。考え直してみます。 ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問