Последовательность С++

151

30 июля 2019, 13:00

Бесконечная числовая последовательность задана с помощью формулы ее k-го элемента:

Ak = k!*2^k, где k = 1, 2, 3,...

Найти сумму N первых элементов этой последовательности по модулю M.

Первая строка входного потока содержит два целых числа N - количество членов последовательности (1 ≤ N ≤ 10^4) и M - модуль (2 ≤ M ≤ 10^9).

В выходной поток вывести сумму N первых элементов заданной последовательности по модулю M.

Пример входного потока: 5 10 Пример выходного потока: 2

#include <iostream>
#include <cmath>
using namespace std;
long fact (long v)
{
  int z=1;
  for (long i=1;i<=v;i++)
  {
    z*=i;
  }
  return z;
}
int main()
{
  long n,m,elem,sum=0;
  cin >> n >> m;
  for (long i=1;i<=n;i++)
  {
    elem=fact(i)*pow(2,i);
    sum+=elem;
  }
  cout << sum%m;
  return 0;
}

Проходит только 1 тест. Подскажите, пожалуйста, что делать? https://acmp.ru/index.asp?main=task&id_task=910

Answer 1

Никогда не задумывались о том, что 10000! - это очень большое число, как и 2 в десятитысячной степени?

Надо все время работать по модулю M, примерно так (не компилировал, просто показать идею - набросал на коленке). unsigned long long нужен, поскольку при ваших значениях легко вылететь за пределы int.

int main()
{
    unsigned long long N, M;
    cin >> N >> M;
    unsigned long long sum = 2, term = 2;
    for(int k = 2; k <= N; ++k)
    {
        term = (term * 2 * k) % M;
        sum = (sum + term) %M;
    }
    cout << sum%M << endl;
}

P.S. Я тут прикинул - для N = 10000 эта сумма - примерно 5.6787516480462*1038669.

Answer 2

С++ пересечение массивов (там ответить не могу):

#include <vector>
#include <algorithm>
#include <functional> 
#include <iostream>
using namespace std;
vector<int>::iterator intersect(vector<int> a1, vector<vector<int>> a, size_t& n, vector<int>*& p, vector<int>::iterator* j = nullptr)
{
    vector<int> r;
    if (++n >= a.size()) {
        if (p && j) {
            for (vector<int>::iterator k = p->begin(); k != *j; k++)
                r.push_back(*k);
            p = new vector<int>(r);
            return p->end();
        }
        p = &r;
        return r.begin();
    }
    p = &r;
    r.resize(std::min(a1.size(), a[n].size()));
    sort(a[n].begin(), a[n].end(), greater<int>());
    vector<int>::iterator i = set_intersection(a1.begin(), a1.end(), a[n].begin(), a[n].end(), r.begin(), greater <int>());
    return intersect(r, a, n, p, &i);
}
int main()
{ 
    vector<vector<int>> a = { {1,2,3},{4,3,5},{7,8,3} };
    size_t n = 0;
    vector<int>* p = nullptr;
    sort(a[0].begin(), a[0].end(), greater<int>());
    vector<int>::iterator i = intersect(a[0], a, n, p);
    if (!p) return 1;
    for (vector<int>::iterator j = p->begin(); j != i; j++)
        cout << *j << " ";
    delete p;
    char c;
    cin >> c;
    return 0;
}