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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

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

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

3649閲覧

「冪乗の剰余」を求めたい。

s8079

総合スコア36

C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

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

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2016/11/19 13:32

編集2016/12/03 06:04

###前提・実現したいこと
「冪乗の剰余」を求めたいです。
例えば,「2^3 * 3^3」の場合は計算すると216であり,約数の総和は600です。
これを「1000003」で割った余りは600です。
入力は,
2,3 3,3(底,冪␣底,冪…)
という感じです。
出力は,
600
のように1000003で割った余りを出力します。
入力の最小値は「1^1」です。
入力の最大値は「2^80 + 3^40 + 5^20 + 7^10」です。
ソースコードを提示していただければ自分で解読します。
アルゴリズムのヒントでもいいので教えていただけると幸いです。
###発生している問題・エラーメッセージ
桁数が大きくなりすぎて計算することができません。
###該当のソースコード

C++

1#include <algorithm> 2#include <iostream> 3#include <sstream> 4#include <string> 5#include <vector> 6std::vector<std::pair<int, int>> input(std::string str) { 7 std::pair<int, int> ex; 8 std::stringstream ss; 9 std::vector<std::pair<int, int>> exs; 10 std::replace(str.begin(), str.end(), ',', ' '); 11 ss << str; 12 while (ss >> ex.first >> ex.second) { 13 exs.push_back(ex); 14 } 15 return exs; 16} 17int main(void) { 18 std::string str; 19 while (std::getline(std::cin, str)) { 20 std::vector<std::pair<int, int>> exs(input(str)); 21 long long int mul = 1; 22 for (const std::pair<int, int> ex : exs) { 23 long long int sum = 0; 24 for (int i = 0; i <= ex.second; ++i) { 25 sum += pow(ex.first, i); 26 } 27 mul *= sum; 28 } 29 std::cout << mul % 1000003 << std::endl; 30 } 31 return EXIT_SUCCESS; 32}

###試したこと
そのまま割ってみました。
###補足情報(言語/FW/ツール等のバージョンなど)
言語:C++11

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

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

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

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

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

ozwk

2016/11/19 13:36

「2^3 + 3^3」<-素因数分解?
MasahikoHirata

2016/11/19 13:54

ozwkさん、ソースを読み取ると。。。にしても設問が読み取りにくい。
swordone

2016/11/19 14:05 編集

これ、CodeIQの川添さんの問題のように見えるのですが、期間中にこう言うところで質問するのはルール違反では?
s8079

2016/11/19 14:22

この問題には答えていただかなくてもいいです。 お騒がせしました。 つきましては質問は削除すべきなのでしょうが方法が分かりません。
toutou

2016/11/19 14:52

ヘルプには質問を消せると書いてあるんですが、ゴミ箱はみつからないですね。他人からの通報しかないのでしょうかな?
swordone

2016/11/19 15:25

ごみ箱が出るのは自分の質問のみ。
MasahikoHirata

2016/11/19 15:37 編集

swordoneさん、質問に興味があったので早速CodeIQに登録してみました。出題はどこを見れば良いのですか?そっちが気になる。
MasahikoHirata

2016/11/20 06:41

swordoneさん、ありがとうございます。問題がまったくそのままでした。またサイトでは勉強になる問題もありがとうございました。
guest

回答2

0

あえてヒントを言うなら、
「新課程の数学A」

投稿2016/11/19 14:25

swordone

総合スコア20649

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

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

0

ベストアンサー

剰余演算には、剰余演算の等価性という性質があります。割り算(分数)以外は簡単に計算することができます。

和と積の剰余はそれぞれの剰余の和と積の剰余と等しいと言う性質から次のようになります。

(2^3 * 3^3) % 1000000 = ((2^3) % 1000000 * (3^3) % 1000000) % 1000000 = ((2 * 2 * 2) % 1000000 * (3 * 3 * 3) % 1000000) % 1000000 = ((((2 % 1000000) * (2 % 1000000) * (2 % 1000000)) % 1000000 * ((3 % 1000000) * (3 % 1000000) * (3 % 1000000)) % 1000000) % 1000000

実際計算するときはオーバーフローしないように、積や和を行う度に剰余を求める必要があります(上の式では一部の積の後の剰余を省略していますが、計算する数によっては必要です)。また、1000000で割った値は2147483647(2^31-1)以下ですが、それらの積は2147483647を越える場合がありますので、64bit以上であることが保証されたlong longint_least64_tを使うようにしてください。

余談ですが、割り算の場合は、剰余する数(法)が素数の場合のみ計算できるため、この系の問題が多い競技プログラミングでは法に10^9+7(素数)が使われる場合が多いです。


問題文ちゃんとみてなかった…。約数の総和でしたね。上は一番大きい約数、つまり、その数自身です。他の約数も同じように計算して足して剰余するだけです。

ですが、単純に一つ一つ計算した場合、たぶん、間に合いません。ではどうすするかなのですが、なんかCodeIQの問題っぽいので、12月01日(木)AM10:00の締め切りすぎてから、続きを書きます。


解説がすでにあるようですが、私は読んでません。間違っているかもです。

さて、「あとは各約数を一つ一つ計算して足すだけ」という話でしたが、それでは間に合わないだろうという話でした。ここからどうするかです。

まずは、計算量を減らすことを考えます。素因数分解された素数に対するそれぞれの数はn0, n1, n2, ... piとすると、約数だけで(n0 + 1) * (n1 + 1) * (n2 + 1) * ... * (pi + 1)個もあります。膨大な数です。これらを足して行くだけでもかなりの計算量です。しかも、それぞれの約数について計算しなければなりません。ということで、約数の総和について公式を用いて、計算数を減らすようにします。

p0^n0p1^n2p2^n2*... pi^ni
と素因数分解できるある数の約数の総和は
(p0^0 + p0^1 + .. + p0^n0) * (p1^0 + p1^1 + .. + p1^n1) * (p2^0 + p2^1 + .. + p2^n2) * ... * (pi^0 + pi^1 + .. + pi^ni)
で求められます。

それぞれはn回で、それが(i+1)個あるのでn0 + n1 + n2 + ... + ni + i回の計算で可能になります。掛け算から足し算ですので、かなり回数が減りました。

さて、これでもまだ不十分です。それぞれの冪乗計算が(n0 + 1) + (n1 + 1) + (n2 + 1) + ... + (pi + 1)個もあります。しかも、これらは個々にオーバーフローの可能性があるので、冪乗を計算してからmodをとることはできません。p^nをまともに計算したらO(log n)になるので、間に合いません。そこで使うのはメモ化です。まずは、次の式が成り立つことに注目します。

p^n mod D = (p^(n-1) * p) mod D = (p^(n-1) mod D) * (p mod D) mod D

p^n mod Dを計算するときp^(n-1) mod Dがわかっていれば、p mod Dをかけて、mod Dするだけで済みます。nを0から順番に計算するのであれば、一つ前のp^(n-1) mod Dは計算済みのはずです。つまり、この計算済みの値を別途保存しておけば、次の値もすぐに求められると言うことです。この方法であれば、どんなにnが大きくなってもそれぞれはO(1)で計算できると言うことになります。この前に計算していた値を保存して使う方法をメモ化といいます。

こうして最終的な計算量はO(n0 + n1 + n2 + ... + ni)になり、たぶん、間に合うようになるでしょう。

投稿2016/11/19 13:59

編集2016/12/03 07:13
raccy

総合スコア21733

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

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

swordone

2016/11/19 14:03 編集

> 割り算の場合は、剰余する数(法)が素数の場合のみ計算できるため ここの意味が知りたいです。 計算は素数でなくても出来るのでは?
s8079

2016/11/19 14:16

この問題には答えていただかなくてもいいです。 お騒がせしました。 つきましては質問は削除すべきなのでしょうが方法が分かりません。
raccy

2016/11/19 14:28

私も詳しく説明できないんですが、(a/b)%nをa/bを計算せずに求めるにはnが素数でなくてはならないらしいです(aはbで割り切れることが前提)。nCrな組み合わせ問題とかは、aやbがlong longを越えるような値になるので多倍長整数でも使わない限りa/bは計算できません(そして使ったとしても、遅すぎて間に合いません)。方法を知らないと解けない…と言うことです。実際の計算は下記を参考にしてみてください。 http://nagoyacoder.web.fc2.com/topcoder/topcoder_cpp4.html
swordone

2016/11/19 14:52

割り算の剰余の性質ということを見落としていました。 しかしこの質問が本当にCodeIQのものなら、使えるかもしれない(法が1000003で素数)
swordone

2016/11/19 16:06

調べてみたら、「モジュラ逆数」というものらしいですね。これが存在するためには、bとnが「互いに素」でなくてはなりませんが、様々なbに対応するためにはnは素数(ただし、bがn未満である必要あり)でなくてはいけないと。
swordone

2016/12/03 07:49 編集

あの問題、本当は(n!)^n(ただし1≦n≦1000)の約数の総和を1000003で割った余りを求める問題だったのですが、 この解法を知っているからこそ素因数分解という発想に至れると思うのですが、そうでないなら質問者はなぜ素因数分解したんだろう…。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問