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

Обсуждение задачи 1091. Tmutarakan Exams

I think I have problem with the __int64 type. Can anyone help me?
Послано Kolio 29 апр 2003 19:46
I've solved this problem in two different ways. I've tested the both
sollutions on my computer (I use Visual C++ 6.0) and they give the
same results on all the possible tests, but this one give WA and the
other is ACC. What's the problem with this? Maybe the __int64 type?
Can anyone help me?

#include <stdio.h>

#define N 64

int k,s;

int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53};

__int64 nad[N][N];
//nad[i][j] is the number of the subsets with j elements of a set
//with i elements
void initnad(void)
{
    nad[1][0] = nad[1][1] = 1;
    for(int i = 2; i<=s; i++)
    {
        nad[i][0] = nad[i][i] = 1;
        for(int j=1; j<i; j++)
            nad[i][j] = nad[i-1][j] + nad[i-1][j-1];
    }
}

bool hassquare(int a)
{
    for(int i=0; prime[i]*prime[i] <= a; i++)
        if( a% (prime[i]*prime[i]) == 0 )
            return 1;

    return 0;
}

int doit(void)
{
    __int64 res = 0;
    for(int i=2; i<=s; i++)
    {
        if( hassquare(i) )
            continue;

        __int64 cur = nad[s/i][k];

        int dels = 0;
        for(int j=0; prime[j]<=i; j++)
            dels += !(i%prime[j]);

        if( dels%2 )
            res += cur;
        else
            res -= cur;

    }

    res = (res>10000)?10000:res;
    return (int)res;
}

int main(void)
{
    scanf("%d%d", &k, &s);
    initnad();
    printf("%d\n", doit());

    return 0;
}