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

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


В последовательности чисел a1, a2, a3, ... задан первый член, а остальные вычисляются по формуле ai = (ai - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a1 < 10 000, 1 <= N <= 2 000 000 000.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
 
using namespace std;
 
int n;
vector<int> mas;
map<int,int> mem; // value, index
int osn = 10000;
void input()
{
    int first;
    cin>>first>>n;
    n--;
    mas.resize(osn);
 
    mas[0] = first;
    mem[first] = 0;
}
void solve()
{
    map<int,int>::iterator it;
    int base = -1;   // first period first element index
    int perLen = -1; // period length
    for (int i=1;;i++)
    {
        mas[i] = (mas[i-1] * mas[i-1]) % osn;
        it = mem.find(mas[i]);
        if (it != mem.end())
        {
            base = it->second;
            perLen = i - base;
            break;
        }
        else
            mem[mas[i]] = i;
    }
    if (n<=base)
        cout<<mas[n];
    else
    {
        int index = base + (n-base) % perLen;
        cout<<mas[index];
    }
       
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

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



Комментарии

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