ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1860. Фибориалы

tl
Послано for_love 29 апр 2013 22:12
# include <cstdio>
# include <iostream>
# include <vector>
# include <cstring>
# include <algorithm>
# include <map>
# include <string>
# include <set>
# include <cmath>

using namespace std;

const int M = 1e9 + 7;
const int N = 1000001;

int a[N], n, f[N], prime[170], sz;
bool used[N];

void get_primes(){
    for (int i = 2; i < 1001; i ++){
        for (int j = i + i; j < 1001; j += i) used[j] = true;
    }
    for (int i = 2; i < 1001; i ++){
        if (!used[i]) prime[sz++] = i;
    }
}

int main(){

    scanf("%d", &n);
    get_primes();

    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i ++){
        f[i] = f[i - 1] + f[i - 2];
        if (f[i] >= M) f[i] -= M;
    }
    for (int i = n; i > 1; i --){
        int p = i;
        for (int j = 0; j < sz && prime[j] * prime[j] <= p; j ++){
            while (p % prime[j] == 0){
                p /= prime[j];
                a[prime[j]] += f[n - i + 1];
                if (a[prime[j]] >= M) a[prime[j]] -= M;
            }
        }
        if (p > 1){
            a[p] += f[n - i + 1];
            if (a[p] >= M) a[p] -= M;
        }
    }
    long long ans = 1;
    for (int i = 1; i <= n; i ++){
        ans = (ans * long long((a[i] + 1) % M)) % M;
    }
    printf("%lld", ans);

    return 0;
}
Otvet
Послано MUHAMMAD 3 апр 2014 19:16
wrong answer