###前提・実現したいこと
「冪乗の剰余」を求めたいです。
例えば,「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
回答2件
あなたの回答
tips
プレビュー