結果
問題 | No.373 かけ算と割った余り |
ユーザー | dgd1724 |
提出日時 | 2016-10-02 20:09:13 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,549 bytes |
コンパイル時間 | 836 ms |
コンパイル使用メモリ | 103,628 KB |
実行使用メモリ | 261,232 KB |
最終ジャッジ日時 | 2024-05-01 09:38:46 |
合計ジャッジ時間 | 4,245 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,752 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
ソースコード
#define _USE_MATH_DEFINES //M_PI(π),M_SQRT2(√2) #include <iostream> //std::cout, std::cin #include <string> //std::string,std::to_string(C++11) #include <vector> //std::vector #include <valarray> //std::valarray #include <algorithm> //std::sort #include <ctime> //localtime_s #include <cstdlib> //abs #include <cmath> //abs,std::pow,sqrt,sin,cos,round,floor,ceil #include <fstream> //std::ifstream,std::ofstream #include <iomanip> //std::setprecision,std::setw,std::setfill #include <random> //std::random(C++11) #include <numeric> //std::accumulate #include <functional> //std::greater bool Compare_MultiplePrecision(const std::string A, const std::string B) { if (A == B) { return true; } if (A.length() > B.length()) { return true; } else if (A.length() < B.length()) { return false; } else { unsigned int i = 0; while (A[i] == B[i]) { i++; } if (A[i] > B[i]) { return true; } else { return false; } } } std::string Subtract_MultiplePrecision(const std::string A, const std::string B) { int a[100] = {}; int b[100] = {}; int c[200] = {}; for (unsigned int i = 0; i < A.length(); i++) { a[i] = A[A.length() - 1 - i] - '0'; } for (unsigned int i = 0; i < B.length(); i++) { b[i] = B[B.length() - 1 - i] - '0'; } for (unsigned int i = 0; i < A.length(); i++) { if (a[i] >= b[i]) { c[i] = a[i] - b[i]; } else { c[i] = a[i] + 10 - b[i]; b[i + 1]++; } } int st = 199; while (c[st] == 0) { st--; } std::string ans; for (int i = st; i >= 0; i--) { ans += std::to_string(c[i]); } if (ans == "") { ans = "0"; } return ans; } std::string Multiply_MultiplePrecision(const std::string A, const std::string B) { int a[100] = {}; int b[100] = {}; int c[200] = {}; for (unsigned int i = 0; i < A.length(); i++) { a[i] = A[A.length() - 1 - i] - '0'; } for (unsigned int i = 0; i < B.length(); i++) { b[i] = B[B.length() - 1 - i] - '0'; } for (unsigned int i = 0; i < B.length(); i++) { for (unsigned int j = 0; j < A.length(); j++) { c[i + j] += b[i] * a[j]; } } for (unsigned int i = 0; i < A.length() + B.length(); i++) { c[i + 1] += c[i] / 10; c[i] = c[i] % 10; } int st = 199; while (c[st] == 0) { st--; } std::string ans; for (int i = st; i >= 0; i--) { ans += std::to_string(c[i]); } if (ans == "") { ans = "0"; } return ans; } std::string Modulo_MultiplePrecision(const std::string A, const std::string B) { if (!Compare_MultiplePrecision(A, B)) { return A; } std::string rem = A; std::string div; while (rem.length() - B.length() > 1) { div = B; for (unsigned int i = 0; i < rem.length() - B.length() - 1; i++) { div = Multiply_MultiplePrecision(div, "10"); } while (Compare_MultiplePrecision(rem, div)) { rem = Subtract_MultiplePrecision(rem, div); } } while (Compare_MultiplePrecision(rem, B)) { rem = Subtract_MultiplePrecision(rem, B); } return rem; } int main(void) { //test用 //std::ifstream in("123.txt"); //std::cin.rdbuf(in.rdbuf()); std::string A, B, C, D; std::cin >> A >> B >> C >> D; if (A.length() + B.length() + C.length() <= 18) { unsigned long long a = std::stoi(A); unsigned long long b = std::stoi(B); unsigned long long c = std::stoi(C); unsigned long long d = std::stoi(D); std::cout << (a*b*c) % d << std::endl; } else { std::string ans; ans = Multiply_MultiplePrecision(A, B); ans = Multiply_MultiplePrecision(ans, C); ans = Modulo_MultiplePrecision(ans, D); std::cout << ans << std::endl; } }