Сложение чисел до определенного разряда

struct BillionNum : public std::vector<unsigned>{
    static const unsigned MaxDigit = 1000000000;
 
    BillionNum(unsigned x){
        push_back(x); // первые 9 цифр
        push_back(x); // последние 9 цифр
    }
 
    // add a big number
    void operator+=(BillionNum& other){
        if (other[0] + (*this)[0] > MaxDigit){
            (*this)[0] /= 10;
            other[0] /= 10;
            (*this)[0] += other[0];
        }
        else (*this)[0] += other[0];
        (*this)[1] += other[1];
        (*this)[1] %= MaxDigit;
    }
};
 
int main(){
    BillionNum a = 1;
    BillionNum b = 1;
 
    for (unsigned int i = 2; i <= 330000; i++){
        a += b;
        swap(a, b);
    }
}

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <fstream>
#include <iterator>
#include <string>
#include <algorithm>
#include <exception>
#include <stdexcept>
#include <cstring>
#include <cstdio>
#include <cstdlib>
 
class BigInteger
{
public:
    BigInteger()
    {
        _data.push_back(0);
    }
 
    BigInteger(long long x)
    {
        while (x)
        {
            _data.push_back(x % _base);
            x /= _base;
        }
 
        if (_data.empty()) _data.push_back(0);
    }
 
    BigInteger(unsigned long long x)
    {
        while (x)
        {
            _data.push_back(x % _base);
            x /= _base;
        }
 
        if (_data.empty()) _data.push_back(0);
    }
 
    BigInteger(int x) : BigInteger((long long)x) {}
    BigInteger(unsigned int x) : BigInteger((unsigned long long)x) {}
    BigInteger(short x) : BigInteger((long long)x) {}
    BigInteger(unsigned short x) : BigInteger((unsigned long long)x) {}
    BigInteger(char x) : BigInteger((long long)x) {}
    BigInteger(unsigned char x) : BigInteger((unsigned long long)x) {}
 
    BigInteger(std::string &s)
    {
        for (int i = (int)s.size(); i > 0; i -= 9)
            if (i < 9)
                _data.push_back(atoi(s.substr(0, i).data()));
            else
                _data.push_back(atoi(s.substr(i - 9, 9).data()));
 
        while (_data.size() > 1 && _data.back() == 0)
            _data.pop_back();
    }
 
    BigInteger(const char *s)
    {
        std::string d = s;
 
        for (int i = (int)d.size(); i > 0; i -= 9)
            if (i < 9)
                _data.push_back(atoi(d.substr(0, i).data()));
            else
                _data.push_back(atoi(d.substr(i - 9, 9).data()));
 
        while (_data.size() > 1 && _data.back() == 0)
            _data.pop_back();
    }
 
    BigInteger(const BigInteger& b)
    {
        _data.resize(b._data.size());
        std::copy(b._data.begin(), b._data.end(), _data.begin());
    }
 
    void ToString(char *s) const
    {
        sprintf(s, "%d", _data.empty() ? 0 : _data.back());
        for (int i = (int)_data.size() - 2; i >= 0; i--)
            sprintf(s, "%s%09d", s, _data[i]);
    }
 
    std::string ToString() const
    {
        char *buff = (char*)malloc(20);
 
        sprintf(buff, "%d", _data.empty() ? 0 : _data.back());
        std::string res = buff;
 
        for (int i = (int)_data.size() - 2; i >= 0; i--)
        {
            sprintf(buff, "%09d", _data[i]);
            res += buff;
        }
 
        free(buff);
 
        return res;
    }
 
    friend const BigInteger operator+(BigInteger &i);
    friend const BigInteger& operator++(BigInteger &i);
    friend const BigInteger& operator--(BigInteger &i);
    friend const BigInteger operator++(BigInteger &i, int);
    friend const BigInteger operator--(BigInteger &i, int);
 
    friend const BigInteger operator+(const BigInteger &c, const BigInteger &b);
    friend const BigInteger operator-(const BigInteger &c, const BigInteger &b);
    friend const BigInteger operator*(const BigInteger &a, const BigInteger &b);
    friend const BigInteger operator/(const BigInteger &a, const BigInteger &b);
    friend const BigInteger operator%(const BigInteger &a, const BigInteger &b);
 
    friend BigInteger& operator+=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator-=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator*=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator/=(BigInteger &a, const BigInteger &b);
    friend BigInteger& operator%=(BigInteger &a, const BigInteger &b);
 
    friend bool operator==(const BigInteger &a, const BigInteger &b);
    friend bool operator<=(const BigInteger &a, const BigInteger &b);
    friend bool operator>=(const BigInteger &a, const BigInteger &b);
    friend bool operator<(const BigInteger &a, const BigInteger &b);
    friend bool operator>(const BigInteger &a, const BigInteger &b);
    friend bool operator!=(const BigInteger &a, const BigInteger &b);
 
    /*operator long long() const
    {
    long long res = 0, b = 1;
    for(size_t i = 0; i < _data.size(); i++)
    {
    res += b * _data[i];
    b *= BigInteger::_base;
    }
    return res;
    }
 
    operator unsigned long long()
    {
    unsigned long long res = 0, b = 1;
    for(size_t i = 0; i < _data.size(); i++)
    {
    res += b * _data[i];
    b *= BigInteger::_base;
    }
    return res;
    }*/
 
    friend std::istream& operator >> (std::istream &is, BigInteger &i)
    {
        std::string s;
        is >> s;
        i = BigInteger(s);
        return is;
    }
 
    friend std::ostream& operator<<(std::ostream &os, const BigInteger &i)
    {
        os << i.ToString();
        return os;
    }
 
private:
    static const int _base = 1000 * 1000 * 1000;
    std::vector<int> _data;
 
    int _cmp(const BigInteger &a, const BigInteger &b) const //a - b, 1 if a > b
    {
        if (a._data.size() > b._data.size()) return 1;
        if (a._data.size() < b._data.size()) return -1;
 
        for (int i = (int)a._data.size() - 1; i >= 0; i--)
        {
            if (a._data[i] > b._data[i]) return 1;
            if (a._data[i] < b._data[i]) return -1;
        }
 
        return 0;
    }
 
    BigInteger _div_short(const BigInteger &c, int b, int &mod) const
    {
        mod = 0;
        BigInteger a = c;
        for (int i = (int)a._data.size() - 1; i >= 0; i--)
        {
            long long cur = a._data[i] + mod * 1ll * BigInteger::_base;
            a._data[i] = int(cur / b);
            mod = int(cur % b);
        }
 
        while (a._data.size() > 1 && a._data.back() == 0)
            a._data.pop_back();
 
        return a;
    }
 
    bool _is_zero() const
    {
        return _data.size() == 1 && _data[0] == 0;
    }
};
 
const BigInteger operator+(const BigInteger &i)
{
    return BigInteger(i);
}
 
const BigInteger& operator++(BigInteger &i)
{
    int j = 0;
    i._data[0]++;
 
    while (i._data[j] >= BigInteger::_base)
    {
        if (j == (int)i._data.size() - 1) i._data.push_back(1); else i._data[j + 1]++;
        i._data[j] -= BigInteger::_base;
        j++;
    }
 
    return i;
}
 
const BigInteger operator++(BigInteger &i, int)
{
    BigInteger old = BigInteger(i);
 
    int j = 0;
    i._data[0]++;
 
    while (i._data[j] >= BigInteger::_base)
    {
        if (j == (int)i._data.size() - 1) i._data.push_back(1); else i._data[j + 1]++;
        i._data[j] -= BigInteger::_base;
        j++;
    }
 
    return old;
}
 
//TODO: Optimize
const BigInteger& operator--(BigInteger &i)
{
    if (!i._is_zero()) i = i - 1;
    return i;
}
 
//TODO: Optimize
const BigInteger operator--(BigInteger &i, int)
{
    BigInteger old = BigInteger(i);
    if (!i._is_zero()) i = i - 1;
    return old;
}
 
const BigInteger operator+(const BigInteger &c, const BigInteger &b)
{
    BigInteger a = c;
 
    int carry = 0;
    for (size_t i = 0; i < std::max(a._data.size(), b._data.size()) || carry; i++)
    {
        if (i == a._data.size()) a._data.push_back(0);
        a._data[i] += carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] >= BigInteger::_base;
        if (carry) a._data[i] -= BigInteger::_base;
    }
 
    return a;
}
 
const BigInteger operator-(const BigInteger &c, const BigInteger &b)
{
    if (c < b) throw std::invalid_argument("a - b, a must b greater or equal zero");
    BigInteger a = c;
 
    int carry = 0;
    for (size_t i = 0; i < b._data.size() || carry; i++)
    {
        a._data[i] -= carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] < 0;
        if (carry) a._data[i] += BigInteger::_base;
    }
 
    while (a._data.size() > 1 && a._data.back() == 0)
        a._data.pop_back();
 
    return a;
}
 
const BigInteger operator*(const BigInteger &a, const BigInteger &b)
{
    BigInteger c;
    c._data.resize(a._data.size() + b._data.size());
 
    for (size_t i = 0; i < a._data.size(); i++)
        for (int j = 0, carry = 0; j < (int)b._data.size() || carry; j++)
        {
            long long cur = c._data[i + j] + a._data[i] * 1ll * (j < (int)b._data.size() ? b._data[j] : 0) + carry;
            c._data[i + j] = int(cur % BigInteger::_base);
            carry = int(cur / BigInteger::_base);
        }
 
    while (c._data.size() > 1 && c._data.back() == 0)
        c._data.pop_back();
 
    return c;
}
 
//TODO: Division by zero
const BigInteger operator/(const BigInteger &a, const BigInteger &b)
{
    if (b._is_zero()) throw std::invalid_argument("division by zero");
    BigInteger l = 0, r = a + 1, m;
    int t;
    while (r - l > 1)
    {
        //m = (r + l) / 2;
        m = a._div_short(r + l, 2, t);
        if (b * m <= a) l = m; else r = m;
    }
    return l;
}
 
const BigInteger operator%(const BigInteger &a, const BigInteger &b)
{
    if (b._is_zero()) throw std::invalid_argument("division by zero");
    BigInteger l = 0, r = a + 1, m;
    int t;
    while (r - l > 1)
    {
        //m = (r + l) / 2;
        m = a._div_short(r + l, 2, t);
        if (b * m <= a) l = m; else r = m;
    }
    return a - b * l;
}
 
BigInteger& operator+=(BigInteger &a, const BigInteger &b)
{
    int carry = 0;
    for (size_t i = 0; i < std::max(a._data.size(), b._data.size()) || carry; i++)
    {
        if (i == a._data.size()) a._data.push_back(0);
        a._data[i] += carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] >= BigInteger::_base;
        if (carry) a._data[i] -= BigInteger::_base;
    }
    return a;
}
 
BigInteger& operator-=(BigInteger &a, const BigInteger &b)
{
    int carry = 0;
    for (size_t i = 0; i < b._data.size() || carry; i++)
    {
        a._data[i] -= carry + (i < b._data.size() ? b._data[i] : 0);
        carry = a._data[i] < 0;
        if (carry) a._data[i] += BigInteger::_base;
    }
 
    while (a._data.size() > 1 && a._data.back() == 0)
        a._data.pop_back();
 
    return a;
}
 
BigInteger& operator*=(BigInteger &a, const BigInteger &b)
{
    a = a * b;
    return a;
}
 
BigInteger& operator/=(BigInteger &a, const BigInteger &b)
{
    a = a / b;
    return a;
}
 
BigInteger& operator%=(BigInteger &a, const BigInteger &b)
{
    a = a % b;
    return a;
}
 
bool operator==(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) == 0;
}
 
bool operator<=(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) <= 0;
}
 
bool operator>=(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) >= 0;
}
 
bool operator<(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) < 0;
}
 
bool operator>(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) > 0;
}
 
bool operator!=(const BigInteger& a, const BigInteger& b)
{
    return a._cmp(a, b) != 0;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::vector<BigInteger> f = { BigInteger(0), BigInteger(1) };
    for (int i = 2; i <= n; i++) f.push_back(f[i - 1] + f[i - 2]);
    std::cout << f[n].ToString() << std::endl;
    return 0;
}

#include <iostream>
#include <vector>
 
//#define ORIGINAL
 
// store single digits with lowest digits first
// e.g. 1024 is stored as { 4,2,0,1 }
struct BillionNum : public std::vector<unsigned int>
{
  // must store exactly 9 digits per cell
  static const unsigned int MaxDigit = 1000000000;
 
  // fill one cell
  BillionNum(unsigned int x)
  {
    push_back(x);
  }
 
  // add a big number
  void operator+=(const BillionNum& other)
  {
    // this code is a 95% copy of my BigNum class
 
    // add in-place, make sure it's big enough
    if (size() < other.size())
      resize(other.size(), 0);
 
    unsigned int carry = 0;
    for (size_t i = 0; i < size(); i++)
    {
      // perform standard addition algorithm
      carry += operator[](i);
      if (i < other.size())
        carry += other[i];
      else
        if (carry == 0)
          return;
 
      if (carry < MaxDigit)
      {
        // no overflow
        operator[](i) = carry;
        carry         = 0;
      }
      else
      {
        // yes, we have an overflow
        operator[](i) = carry - MaxDigit;
        carry         = 1;
      }
    }
 
    if (carry > 0)
      push_back(carry);
  }
};
 
// return true if x is pandigital (1..digits)
bool isPandigital(unsigned int x, unsigned int digits = 9)
{
  unsigned int mask = 0; // zero is not allowed, only 1 to 9
  for (unsigned int i = 0; i < digits; i++)
  {
    // get next digit
    auto current = x % 10;
    if (current == 0 || current > digits)
      return false;
 
    auto bit = 1 << current;
    // already seen ?
    if ((mask & bit) != 0)
      return false;
 
    // mark that digit as "used"
    mask |= bit;
    x    /= 10;
  }
 
  return true;
}
 
int main()
{
  unsigned int first  = 1; // F_1 = 1
  unsigned int second = 1; // F_2 = 1
  unsigned int digits = 9; // 9-pandigital (1..9)
 
#ifndef ORIGINAL
  std::cin >> first >> second >> digits;
#endif
 
  if (first == 1 && digits == 1)
  {
    std::cout << "1" << std::endl;
    return 0;
  }
 
  unsigned long long Modulo = 1; // 10^digits
  for (unsigned i = 1; i <= digits; i++)
    Modulo *= 10;
 
  // convert to a simplified BigNum
  BillionNum a = first;
  BillionNum b = second;
 
  for (unsigned int i = 2; i <= 2000000; i++)
  {
    // analyze the lowest digits
    auto lowest = b.front() % Modulo;
    bool isPanLow = isPandigital(lowest, digits);
 
    // look at the highest digits
    if (isPanLow)
    {
      unsigned long long highest = b.back();
      // maybe too few digits: use next cells, too
      if (highest < Modulo && b.size() > 1)
        highest = highest * BillionNum::MaxDigit + b[b.size() - 2];
 
      // too many digits ? shrink until we have the right number of digits
      while (highest >= Modulo)
        highest /= 10;
 
      // check if pandigital
      if (isPandigital(highest, digits))
      {
        // yes, pandigital on both ends !
        std::cout << i << std::endl;
        return 0;
      }
    }
 
    // next Fibonacci number
    a += b;
    std::swap(a, b);
 
    // don't compute all digits:
    // - look at the lowest digits
    // - and look at the highest (incl. some of its neighbors because of carry)
    // => remove those in the middle
    // => my "magic numbers" 10 and 2 were chosen pretty much at random ...
    if (a.size() > 10)
    {
      a.erase(a.begin() + 2);
      b.erase(b.begin() + 2);
    }
  }
 
  // failed
  std::cout << "no solution" << std::endl;
  return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
   unsigned long long int a=1, b=1, k;
   int n;
   string s;
 
   do
   {
   cout <<"n="; cin >>n;
   if (n<1 || n>90) cout <<"1<=n<=90, Repeat please...\n";
   }
   while (n<1 || n>90);
    
   cout <<1<<"\n"<<1<<"\n";
   for(int i = 1; i <= n; i++)
     {
     k=a+b;
     a=b;
     b=k;
     s = to_string(k);
     string s1(s, 0, 9);
     cout <<s1<<"\n";
     }  
system("pause");
return 0;
}