Решение задачи Деление длинного числа на короткое с Меньшиков

Без пояснения   Просмотров: 26


Даны целое неотрицательное число M и целое положительное число N. Найти M div N и M mod N.

Код

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int len = 7;
char* param = "%0.7d";
const int osn = pow(10.0,len);
const int max_len = 10000;
struct BigInt{
    long long digits[max_len];
    int amount;
    BigInt()
    {
        memset(digits,0,sizeof(digits));
        amount = 1;
    }
    void input()
    {
        string str;
        cin>>str;
        int pos = 0;
        for (int i=str.size()-1;i>=0;i-=len)
        {
            int start = i - (len - 1);
            if (start<0) start = 0;
            digits[pos++] = atoi(str.substr(start,i - start + 1).c_str());;
        }
        amount = pos;
    }
    void output()
    {
        printf("%d",digits[amount-1]);
        for (int i=amount-2;i>=0;i--)
            printf(param,digits[i]);
    }
};
void DivMod(const BigInt &a,const int &n, BigInt &div, int &mod)
{
    long long r = 0;
    for (int i=a.amount-1;i>=0;i--)
    {
        long long tmp = (r*osn + a.digits[i]);
        div.digits[i] = tmp/n;
        r = tmp - div.digits[i]*n;
    }
    int pos = a.amount;
    while (pos !=0 && !div.digits[pos])
        pos--;
    div.amount = pos+1;
    mod = r;
}
int main(){
    BigInt a,div;
    int n,mod;
    a.input(); cin>>n;
    DivMod(a,n,div,mod);   
    div.output();
    cout<<endl<<mod;
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться