Okorosso

деление длинного на короткое

May 6th, 2021
1,033
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <vector>
  3. #include <string>
  4. #include <ostream>
  5. #include <iomanip>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. static const int BASE = 1000000000; // система счистления
  11. static const int baseLen = 9; // длина основания
  12.  
  13. struct LongInteger {
  14.     vector<unsigned long long> digits; // вектор, в котором лежат разряды чисел
  15.     bool negative; //знак числа
  16. };
  17.  
  18. struct divStruct { // структура, которая нам нужна для возвращения результатов деления
  19.     LongInteger li; // лнам
  20.     unsigned long long int mod; // остаток
  21. };
  22.  
  23. void remove_zeros(LongInteger val) { // удаление ведущих нулей
  24.     while (val.digits.size() > 1 && val.digits.back() == 0) {
  25.         val.digits.pop_back();
  26.     }
  27.  
  28.     if (val.digits.size() == 1 && val.digits[0] == 0)
  29.         val.negative = false;
  30. }
  31.  
  32. LongInteger create_li(string s) { //создаем переменную лонгит
  33.     LongInteger num; //запись результатп
  34.     if (s.length() == 0)
  35.         num.negative = false;
  36.  
  37.     else {
  38.         if (s[0] == '-') {
  39.             s = s.substr(1); //начинаем с индекса 1
  40.             num.negative = true;
  41.         } else
  42.             num.negative = false;
  43.  
  44.         for (long long i = s.length(); i > 0; i -= baseLen) {
  45.             if (i < baseLen)
  46.                 num.digits.push_back(atoi(s.substr(0, i).c_str())); // последние элементы добавляем от 0 до i
  47.             else
  48.                 num.digits.push_back(atoi(s.substr(i - baseLen,
  49.                                                    baseLen).c_str())); // крайние 9 элемнтов в первую ячейку запихиваем(запись числа с конца)
  50.         }
  51.     }
  52.     remove_zeros(num); // вызываем функцию
  53.     return num;
  54. }
  55.  
  56. void output(ostream &os, const LongInteger &li) { //поток вывода в аргуманта
  57.     if (li.digits.empty()) // если пустой
  58.         os << 0;
  59.     else {
  60.         if (li.digits.size() == 1) {
  61.             os << li.digits[0];
  62.             return;
  63.         }
  64.         os << li.digits.back(); // выводим с конца
  65.         char old_fill = os.fill('0'); // заполняю чар нулями
  66.  
  67.         for (unsigned long long i = (li.digits.size() - 2); i >= 0; i--) // выводим число
  68.             if (i <= li.digits.size() - 2)
  69.                 os << setw(baseLen) << li.digits[i]; // сколько нужно вывести
  70.             else {
  71.                 os.fill(old_fill); // заполняем промежутки нулями
  72.                 return;
  73.             }
  74.     }
  75. }
  76.  
  77.  
  78. divStruct div_long_and_short(LongInteger left, unsigned long long int b) { // функция деления длинного на короткое
  79.     unsigned long long carry = 0; // остаток. по умолчанию 0
  80.     LongInteger a = std::move(left); // создаем копию лнама, чтобы не менять данный
  81.     for (int i(a.digits.size() - 1); i >= 0; i--) { // идем с конца лнама
  82.         unsigned long long cur = a.digits[i] + carry * BASE; // в текущее число записываем остаток,
  83.         // умноженный на основание + число в текущей ячейке
  84.  
  85.         a.digits[i] = (unsigned long long) (cur / b); // записываем в ячейку див текущего числа на короткое
  86.         carry = (unsigned long long) (cur % b); // в остаток кладем остаток :)
  87.     }
  88.     while (a.digits.size() > 1 and a.digits.back() == 0) { // избавляемся от незначащих нулей, если они есть
  89.         a.digits.pop_back();
  90.     }
  91.     divStruct toReturn; // создаем структуру для возварата ответа
  92.     toReturn.li = a; // в лнам кладем результат
  93.     toReturn.mod = carry; // остаток
  94.     return toReturn;
  95. }
  96.  
  97.  
  98. int main() {
  99.     ifstream fin("input.txt");
  100.     ofstream fout("output.txt");
  101.  
  102.     string n1;
  103.     long long a2;
  104.  
  105.     fin >> n1;
  106.     fin >> a2;
  107.  
  108.     LongInteger a1 = create_li(n1);
  109.     divStruct divRes = div_long_and_short(a1, a2);
  110.     LongInteger a3 = divRes.li;
  111.  
  112.     // вывод
  113.     output(fout, a3);
  114.     fout << '\n' << divRes.mod;
  115. }
RAW Paste Data