teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問「冪乗の剰余」を求めたい。

編集履歴

質問編集履歴

6

タイトル変更

2016/12/03 06:04

投稿

s8079
s8079

スコア36

test CHANGED
@@ -1 +1 @@
1
- 「素因数分解された値の約数の総和の剰余」を求めたい。
1
+ 「冪乗の剰余」を求めたい。
test CHANGED
@@ -1,6 +1,6 @@
1
1
  ###前提・実現したいこと
2
2
 
3
- 「素因数分解された大きな値の約数の総和の剰余」を求めたいです。
3
+ 「冪乗の剰余」を求めたいです。
4
4
 
5
5
  例えば，「2^3 * 3^3」の場合は計算すると216であり，約数の総和は600です。
6
6
 

5

タグの変更

2016/12/03 06:04

投稿

s8079
s8079

スコア36

test CHANGED
File without changes
test CHANGED
File without changes

4

再開

2016/12/03 02:49

投稿

s8079
s8079

スコア36

test CHANGED
@@ -1 +1 @@
1
- 質問の削除の方法を知りたい。
1
+ 「素因数分解された値の約数の総和の剰余」を求めたい。
test CHANGED
@@ -1,9 +1,109 @@
1
- 質問は取り消させていただきます。
1
+ ###前提・実現したいこと
2
2
 
3
- フォームより問い合わせたところ，**回答のついていない**質問は右下「編集ボタン」の左にゴミ箱のアイコンが表示されるようです。
3
+ 「素因数分解された大きな値の約数の総和の剰余」を求めたいです。
4
4
 
5
- 残念ながら，現在，回答の付いた質問を削除する手段はないようです。
5
+ 例えば，「2^3 * 3^3」の場合は計算すると216であり，約数の総和は600です。
6
6
 
7
- 取り消させていただいた質問に関しては，11月いっぱいは現状維持とさせていただきます。
7
+ これを「1000003」で割った余りは600です。
8
8
 
9
+ 入力は，
10
+
11
+ `2,3 3,3`(底,冪␣底,冪…)
12
+
13
+ という感じです。
14
+
15
+ 出力は，
16
+
17
+ `600`
18
+
19
+ のように1000003で割った余りを出力します。
20
+
21
+ 入力の最小値は「1^1」です。
22
+
23
+ 入力の最大値は「2^80 + 3^40 + 5^20 + 7^10」です。
24
+
25
+ ソースコードを提示していただければ自分で解読します。
26
+
27
+ アルゴリズムのヒントでもいいので教えていただけると幸いです。
28
+
29
+ ###発生している問題・エラーメッセージ
30
+
31
+ 桁数が大きくなりすぎて計算することができません。
32
+
33
+ ###該当のソースコード
34
+
35
+ ```C++
36
+
37
+ #include <algorithm>
38
+
39
+ #include <iostream>
40
+
41
+ #include <sstream>
42
+
43
+ #include <string>
44
+
45
+ #include <vector>
46
+
47
+ std::vector<std::pair<int, int>> input(std::string str) {
48
+
49
+ std::pair<int, int> ex;
50
+
51
+ std::stringstream ss;
52
+
53
+ std::vector<std::pair<int, int>> exs;
54
+
55
+ std::replace(str.begin(), str.end(), ',', ' ');
56
+
57
+ ss << str;
58
+
59
+ while (ss >> ex.first >> ex.second) {
60
+
61
+ exs.push_back(ex);
62
+
63
+ }
64
+
65
+ return exs;
66
+
67
+ }
68
+
69
+ int main(void) {
70
+
71
+ std::string str;
72
+
73
+ while (std::getline(std::cin, str)) {
74
+
75
+ std::vector<std::pair<int, int>> exs(input(str));
76
+
77
+ long long int mul = 1;
78
+
79
+ for (const std::pair<int, int> ex : exs) {
80
+
81
+ long long int sum = 0;
82
+
83
+ for (int i = 0; i <= ex.second; ++i) {
84
+
85
+ sum += pow(ex.first, i);
86
+
87
+ }
88
+
89
+ mul *= sum;
90
+
91
+ }
92
+
93
+ std::cout << mul % 1000003 << std::endl;
94
+
95
+ }
96
+
97
+ return EXIT_SUCCESS;
98
+
99
+ }
100
+
101
+ ```
102
+
103
+ ###試したこと
104
+
9
- 大変ご迷惑をおかけします。
105
+ そのまま割ってみました。
106
+
107
+ ###補足情報(言語/FW/ツール等のバージョンなど)
108
+
109
+ 言語:C++11

3

タグを変更

2016/12/03 02:47

投稿

s8079
s8079

スコア36

test CHANGED
File without changes
test CHANGED
@@ -1,3 +1,9 @@
1
1
  質問は取り消させていただきます。
2
2
 
3
+ フォームより問い合わせたところ，**回答のついていない**質問は右下「編集ボタン」の左にゴミ箱のアイコンが表示されるようです。
4
+
5
+ 残念ながら，現在，回答の付いた質問を削除する手段はないようです。
6
+
7
+ 取り消させていただいた質問に関しては，11月いっぱいは現状維持とさせていただきます。
8
+
3
- 削除の方法等を教えていただけると助かります。
9
+ 大変ご迷惑をおかけします。

2

質問を削除

2016/11/24 13:22

投稿

s8079
s8079

スコア36

test CHANGED
@@ -1 +1 @@
1
- 「素因数分解された大きな値の約数の総和の剰余」を求めたい。
1
+ 質問の削除の方法を知りたい。
test CHANGED
@@ -1,129 +1,3 @@
1
- ###前提・実現したいこと
1
+ 質問は取り消させていただきます。
2
2
 
3
- 「素因数分解された大きな値の約数の総和の剰余」を求めたいです。
4
-
5
- 例えば，「2^3 * 3^3」の場合は計算すると216であり，約数の総和は600です。
6
-
7
- これを「1000000」で割った余りは600です。
8
-
9
- 入力は，
10
-
11
- `2,3 3,3`(底,冪␣底,冪…)
12
-
13
- という感じです。
14
-
15
- 出力は，
16
-
17
- `600`
18
-
19
- のように1000000で割った余りを出力します。
20
-
21
- 入力の最小値は「1^1」です。
22
-
23
- 入力の最大値は「2^80 + 3^40 + 5^20 + 7^10」です。
24
-
25
- |入力|出力|
26
-
27
- |:----------:|:-----------:|
28
-
29
- |`2,80 3,40 5,20 7,10`|`410267`|
30
-
31
- |`2,360 3,160 5,80 7,40 11,20 13,20 17,20 19,20`|`704575`|
32
-
33
- |`2,780 3,420 5,210 7,120 11,60 13,60 17,30 19,30 23,30 29,30`|`440245`|
34
-
35
- |`2,80 3,40 5,20 7,10`||
36
-
37
- ソースコードを提示していただければ自分で解読します。
3
+ 削除の方法等を教えていただけると助かります。
38
-
39
- アルゴリズムのヒントでもいいので教えていただけると幸いです。
40
-
41
-
42
-
43
- ###発生している問題・エラーメッセージ
44
-
45
- 桁数が大きくなりすぎて計算することができません。
46
-
47
-
48
-
49
- ###該当のソースコード
50
-
51
- ```C++
52
-
53
- #include <algorithm>
54
-
55
- #include <iostream>
56
-
57
- #include <sstream>
58
-
59
- #include <string>
60
-
61
- #include <vector>
62
-
63
- std::vector<std::pair<int, int>> input(std::string str) {
64
-
65
- std::pair<int, int> ex;
66
-
67
- std::stringstream ss;
68
-
69
- std::vector<std::pair<int, int>> exs;
70
-
71
- std::replace(str.begin(), str.end(), ',', ' ');
72
-
73
- ss << str;
74
-
75
- while (ss >> ex.first >> ex.second) {
76
-
77
- exs.push_back(ex);
78
-
79
- }
80
-
81
- return exs;
82
-
83
- }
84
-
85
- int main(void) {
86
-
87
- std::string str;
88
-
89
- while (std::getline(std::cin, str)) {
90
-
91
- std::vector<std::pair<int, int>> exs(input(str));
92
-
93
- long long int mul = 1;
94
-
95
- for (const std::pair<int, int> ex : exs) {
96
-
97
- long long int sum = 0;
98
-
99
- for (int i = 0; i <= ex.second; ++i) {
100
-
101
- sum += pow(ex.first, i);
102
-
103
- }
104
-
105
- mul *= sum;
106
-
107
- }
108
-
109
- std::cout << mul % 1000000 << std::endl;
110
-
111
- }
112
-
113
- return EXIT_SUCCESS;
114
-
115
- }
116
-
117
- ```
118
-
119
-
120
-
121
- ###試したこと
122
-
123
- そのまま割ってみました。
124
-
125
-
126
-
127
- ###補足情報(言語/FW/ツール等のバージョンなど)
128
-
129
- 言語:C++11

1

前提条件の訂正

2016/11/19 14:32

投稿

s8079
s8079

スコア36

test CHANGED
@@ -1 +1 @@
1
- 「素因数分解された大きな値の剰余」を求めたい。
1
+ 「素因数分解された大きな値の約数の総和の剰余」を求めたい。
test CHANGED
@@ -1,8 +1,8 @@
1
1
  ###前提・実現したいこと
2
2
 
3
- 「素因数分解された大きな値の剰余」を求めたいです。
3
+ 「素因数分解された大きな値の約数の総和の剰余」を求めたいです。
4
4
 
5
- 例えば，「2^3 + 3^3」の場合は計算すると600です。
5
+ 例えば，「2^3 * 3^3」の場合は計算すると216であり，約数の総和は600です。
6
6
 
7
7
  これを「1000000」で割った余りは600です。
8
8