Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- //speed coding handle
- #define mp make_pair
- #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " "; }cout << "\n";} ;
- #define f first
- #define s second
- #define loop(i, x, n) for (int i = x; i < n; i++)
- #define joop(x, n) for (ll j = x; j < n; j++)
- #define lp(n) for (ll i = 0; i < n; i++)
- #define err cout << "ERROR" << endl;
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define sz(x) x.size()
- #define rndm rng()
- // types
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define vvi vector<vector<int>>
- #define vvll vector<vector<ll>>
- typedef long long ll;
- typedef long double ld;
- // types of data
- #define inf 1000000000
- #define infll 1000000000000000000
- #define INF ll(1e18)
- #define md 998244353
- #define mod 1000000009
- //#define K 239017
- #define DEBUG 1
- using namespace std;
- mt19937_64 rng(113113);
- uniform_int_distribution<ll> drist;
- // code
- struct bignumber // описание узла
- {
- short digit; // цифра
- bignumber* next; // поле для связи со следующей цифрой числа
- };
- bignumber* create(string str) // создание большого числа из текстовой строки
- {
- bignumber* p, * top = nullptr;
- int i;
- for (i = 0; i < str.size() ; i++)
- {
- p = new bignumber;
- p->digit = short(str[i]) - short('0');
- p->next = top;
- top = p;
- }
- return top;
- }
- void print(const bignumber* BigNum) // рекурсивная распечатка цифр числа
- {
- if (BigNum != nullptr) // если ещё не конец числа
- {
- print(BigNum->next); //вызываем печать для старшего разряда
- cout << BigNum->digit; //печать текущего разряда
- }
- }
- void clear(bignumber** BigNum) // очистка стека (удаление всех узлов из стека)
- {
- bignumber* temp;
- while (*BigNum != nullptr) // пока не достигли конца
- {
- temp = (*BigNum)->next; // устанавливаем указатель temp на следующий элемент
- delete* BigNum;
- *BigNum = temp; // переводим указатель на следующий элемент
- }
- }
- int dlina(bignumber* BigNum)
- {
- int k = 0;
- while (BigNum != nullptr)
- {
- k++;
- BigNum = BigNum->next;
- }
- return k;
- }
- bool Eq(bignumber* BigNum1, bignumber* BigNum2) //проверка, что BigNum1=BigNum2
- {
- if (dlina(BigNum1) != dlina(BigNum2)) return false;
- else //если одинаковое число разрядов
- {
- bool fl = true;
- while (BigNum1 != nullptr)//проверяем совпадение цифр
- {
- if (BigNum1->digit != BigNum2->digit) { fl = false; break; }
- BigNum1 = BigNum1->next;
- BigNum2 = BigNum2->next;
- }
- return fl;
- }
- }
- int sravn(bignumber* BigNum1, bignumber* BigNum2)
- {//если равное число разрядов, сравниваем цифры
- if (BigNum1 == nullptr) return 0;
- else
- {
- int k = sravn(BigNum1->next, BigNum2->next);
- if (k != 0) return k;
- else //k=0, старшие разряды были одинаковые
- return BigNum1->digit - BigNum2->digit;
- }
- }
- bool More(bignumber* BigNum1, bignumber* BigNum2) //BigNum1>BigNum2
- {
- int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
- if (d1 < d2) return false;
- if (d1 > d2) return true;
- //если одинаковое число разрядов
- int k = sravn(BigNum1, BigNum2);
- if (k > 0) return true;
- return false;
- }
- bool Less(bignumber* BigNum1, bignumber* BigNum2) //BigNum1<BigNum2
- {
- int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
- if (d1 < d2) return true;
- if (d1 > d2) return false;
- //если одинаковое число разрядов
- int k = sravn(BigNum1, BigNum2);
- if (k < 0) return true;
- return false;
- }
- bool LessEq(bignumber* BigNum1, bignumber* BigNum2) //BigNum1<=BigNum2
- {
- int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
- if (d1 < d2) return true;
- if (d1 > d2) return false;
- //если одинаковое число разрядов
- int k = sravn(BigNum1, BigNum2);
- if (k <= 0) return true;
- return false;
- }
- bool MoreEq(bignumber* BigNum1, bignumber* BigNum2) //BigNum1>BigNum2
- {
- int d1 = dlina(BigNum1), d2 = dlina(BigNum2);
- if (d1 < d2) return false;
- if (d1 > d2) return true;
- //если одинаковое число разрядов
- int k = sravn(BigNum1, BigNum2);
- if (k >= 0) return true;
- return false;
- }
- void addto(bignumber** BigNum1, bignumber* BigNum2)
- {//сложение двух больших чисел с накапливанием в первое
- if (!BigNum2) return;
- short digit = 0, carry = 0;
- bignumber* prev = *BigNum1, * temp = *BigNum1;
- bignumber* p = nullptr;
- while ((temp != nullptr))
- {
- //учитываем перенос
- digit = carry;
- if (BigNum2 != nullptr) {
- digit = digit + BigNum2->digit;
- BigNum2 = BigNum2->next; //переходим к следующей цифре 2 числа
- }
- if (temp != nullptr) {
- digit = digit + temp->digit;
- prev = temp;
- temp = temp->next;
- }
- //вычисляем новый перенос
- carry = digit / 10;
- //вычисляем цифру текущего разряда
- digit = digit % 10;
- prev->digit = digit;
- }
- while ((carry > 0) || (BigNum2 != nullptr))//создаем новые разряды в 1 числе
- {
- digit = carry;
- if (BigNum2 != nullptr) {
- digit = digit + BigNum2->digit;
- BigNum2 = BigNum2->next; //переходим к следующей цифре 2 числа
- }
- //вычисляем новый перенос
- carry = digit / 10;
- //вычисляем цифру текущего разряда
- digit = digit % 10;
- p = new bignumber;
- p->digit = digit;
- p->next = nullptr;
- if (prev != nullptr) {//был предшествующий узел
- prev->next = p;
- }
- else {
- if (*BigNum1 == nullptr) *BigNum1 = p;
- }
- prev = p;
- }
- }
- void subtract(bignumber** BigNum1, bignumber* BigNum2)
- {
- if (!BigNum2) return;
- short digit = 0, borrow = 0;
- bignumber* prev = *BigNum1, * temp = *BigNum1;
- bignumber* p = nullptr;
- while (temp != nullptr)
- {
- // Учитываем заем
- digit = borrow + temp->digit;
- if (BigNum2 != nullptr) {
- digit -= BigNum2->digit;
- BigNum2 = BigNum2->next; // Переходим к следующей цифре второго числа
- }
- // Вычисляем новый заем
- borrow = digit < 0 ? -1 : 0;
- // Вычисляем цифру текущего разряда
- digit = (digit + 10) % 10;
- prev->digit = digit;
- temp = temp->next;
- prev = temp;
- }
- }
- bignumber* Mult(bignumber* BigNum, int N, int carry)
- {
- int digit = carry;//прибавляем перенос
- bignumber* p = nullptr;
- if ((carry != 0) || (BigNum != nullptr))
- {
- if (BigNum != nullptr)
- { //умножаем цифру числа на N
- digit = digit + N * (BigNum->digit);
- //переходим к следующей цифре
- BigNum = BigNum->next;
- }
- //вычисляем новый перенос
- carry = digit / 10;
- //вычисляем цифру текущего разряда
- digit = digit % 10;
- //создаем этот разряд
- p = new bignumber;
- p->digit = digit;
- //остальные разряды вычисляем рекурсивно
- p->next = Mult(BigNum, N, carry);
- }
- return p;
- }
- void shift(bignumber** BigNum, int n) //поразрядный сдвиг на n (домножение на 10^n)
- {
- bignumber* temp = *BigNum;
- int i;
- for (i = 0; i < n; i++)
- {
- //создаем новый разряд
- temp = new bignumber;
- temp->digit = 0;
- //подцепляем предыдущие разряды
- temp->next = *BigNum;
- *BigNum = temp;
- }
- }
- bignumber* BigMult(bignumber* BigNum1, bignumber* BigNum2)
- {
- bignumber* p = nullptr, * temp = nullptr;
- if (BigNum1 != nullptr)
- {
- int k = 0; //сдвиг разрядов при умножении
- p = new bignumber;
- p->digit = 0;
- p->next = nullptr;
- while (BigNum2 != nullptr)
- {
- temp = Mult(BigNum1, BigNum2->digit, 0);//умножение 1-го числа на текущую цифру 2го
- shift(&temp, k);
- addto(&p, temp);
- clear(&temp);
- temp = nullptr;
- BigNum2 = BigNum2->next;
- k++;
- }
- }
- return p;
- }
- // с округлением вниз
- bignumber* div(bignumber* sa, bignumber *ba){ // a - b * k = 0 <=> a = bk
- bignumber *zero, *bi, *one, *a, *b;
- a = create("1");
- b = create("1");
- a = BigMult(a, sa);
- b = BigMult(b, ba);
- // скопировал
- zero = create("0");
- bi = create("0");
- one = create("1");
- while(More(a, zero)){ // while(a > 0) / while(a > b) <=>
- addto(&zero, b);
- addto(&bi, one);
- }
- // cout << "xueta:";
- // print(bi);
- // cout << endl;
- return bi;
- }
- void solve(){
- string n = "128";
- cin >> n;
- bignumber *bn, *bi, *bd, *one;
- bn = create(n);
- bi = create("2");
- one = create("1");
- while(More(bn, one)){ // n >= 1
- bignumber *divider;
- divider = div(bn, bi);
- while(Eq(BigMult(divider, bi ), bn)){ // если делится нацело
- divider = div(bn, bi); // частное bn/bi с округлением вниз
- print(bi); // простой делитель
- cout << "\n";
- bn = divider; // разложил
- divider = div(bn, bi); // для проверки, делится ли то, которое сейчас
- }
- addto(&bi, one); // смиотрим некст
- clear(÷r);
- }
- clear(&bn); clear(&bi); clear(&bd); clear(&one);
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- #ifdef DEBUG
- // freopen("text.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- solve();
- return 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement