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

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

ただいまの
回答率

90.40%

  • C++

    4647questions

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

  • アルゴリズム

    532questions

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

  • C++11

    124questions

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

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,441

s8079

score 18

前提・実現したいこと

「冪乗の剰余」を求めたいです。
例えば,「2^3 * 3^3」の場合は計算すると216であり,約数の総和は600です。
これを「1000003」で割った余りは600です。
入力は,
2,3 3,3(底,冪␣底,冪…)
という感じです。
出力は,
600
のように1000003で割った余りを出力します。
入力の最小値は「1^1」です。
入力の最大値は「2^80 + 3^40 + 5^20 + 7^10」です。
ソースコードを提示していただければ自分で解読します。
アルゴリズムのヒントでもいいので教えていただけると幸いです。

発生している問題・エラーメッセージ

桁数が大きくなりすぎて計算することができません。

該当のソースコード

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
std::vector<std::pair<int, int>> input(std::string str) {
   std::pair<int, int> ex;
   std::stringstream ss;
   std::vector<std::pair<int, int>> exs;
   std::replace(str.begin(), str.end(), ',', ' ');
   ss << str;
   while (ss >> ex.first >> ex.second) {
       exs.push_back(ex);
   }
   return exs;
}
int main(void) {
   std::string str;
   while (std::getline(std::cin, str)) {
       std::vector<std::pair<int, int>> exs(input(str));
       long long int mul = 1;
       for (const std::pair<int, int> ex : exs) {
           long long int sum = 0;
           for (int i = 0; i <= ex.second; ++i) {
               sum += pow(ex.first, i);
           }
           mul *= sum;
       }
       std::cout << mul % 1000003 << std::endl;
   }
   return EXIT_SUCCESS;
}

試したこと

そのまま割ってみました。

補足情報(言語/FW/ツール等のバージョンなど)

言語:C++11

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • キャンセル

  • MasahikoHirata

    2016/11/20 15:41

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

    キャンセル

  • 退会済みユーザー

    2016/11/24 22:37

    他のユーザから「意図的に内容が抹消された質問」という指摘を受けました
    解決後に編集機能を用いて質問内容を改変し関係のない内容にしたり、内容を削除する行為は禁止しています。
    投稿していただいた質問は、後に他の誰かが困ったときに助けになる情報資産になると考えるからです。
    「質問を編集する」ボタンから編集を行い、他のユーザにも質問内容が見えるように修正してください。

回答 2

checkベストアンサー

+1

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

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

(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^n0*p1^n2*p2^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 23:52

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

    キャンセル

  • 2016/11/20 01:06

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

    キャンセル

  • 2016/12/03 16:49 編集

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 90.40%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C++

    4647questions

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

  • アルゴリズム

    532questions

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

  • C++11

    124questions

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