Форум программистов, компьютерный форум CyberForum.ru

деления по модулю, остатки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
03.02.2012, 18:49     деления по модулю, остатки #1
для олимпиад часто нужно и до конца не могу разобраться. кто знает продвинутые источники по этой теме, особенно когда mod от разности или деления, например.
( a/b ) % M где точно знаю что а, делится на b нацело.
рассуждаю так a / b = n, a = n * b;
(n * b / b) % M;
b % M = k;
n % M * k / k = n % M = (a / b) % M;
фигню написал, в общем мне нужно как-то преобразовать начальное, чтобы можно было брать остаток у а, т.к. оно большое и без модуля не влезает никуда.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2012, 18:49     деления по модулю, остатки
Посмотрите здесь:

Получить новую матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент C++
Распечатать все числа от 1 до N, у которых остатки от деления на число Z не превышают числа M. C++
Произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами C++
Дана прямоугольная матрица. Получить новую матрицу путём деления всех элементов исходной матрицей на её максимальный по модулю элемент. C++
Получить матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
03.02.2012, 18:54     деления по модулю, остатки #2
дайте ссылку на задачу
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
03.02.2012, 20:00  [ТС]     деления по модулю, остатки #3
http://www.codechef.com/FEB12/problems/WCOUNT
но встречаются задачи постоянно, и с делением и с вычитанием.

Добавлено через 1 минуту
ошибки нет, но и результата нет, я фигню получил.
хотелось что-то типа a % M / b% mod M + b * M или что-то такое

Добавлено через 1 час 3 минуты
никто не может помочь?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.02.2012, 21:18     деления по модулю, остатки #4
Цитата Сообщение от AC-93 Посмотреть сообщение
в общем мне нужно как-то преобразовать начальное, чтобы можно было брать остаток у а, т.к. оно большое и без модуля не влезает никуда.
Что бы можно было брать остаток у a и в то же время невозможно a/b - так не бывает. Для Вашей задачи используйте __int64, и все получится.
Если покажете Ваше решение, то помогут быстрее.
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
03.02.2012, 21:35  [ТС]     деления по модулю, остатки #5
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MODULE 1000000007
 
#define ord(a) (('a' <= a && 'z' >= a)? (a - 'a'):(a - 'A' + 32))
 
int main()
{
    int T, i;
    char arr[501];
    int str[501];
    unsigned long long  int sum, temp;
    scanf("%d", &T);
    for (i = 0; i < T; i++)
    {
        int l, j = 0, k,t;
 
        memset(arr, 0, 501 * sizeof(char)), 
        memset(str, 0, 501 * sizeof(int));
        sum = 1;
        scanf("%s", &arr);
        l = strlen(arr);
        for (j = 0; j < l; ++j)
            str[ord(arr[j])]++;
        k = 0;
        for (j = 0; j < 90; ++j)
        {
            int fact = str[i];
            t = 1;
            temp = 1;
            //
                //
            while (fact)
                t *= fact--;
            while (str[j]-- != 0)
            {
                k++;
                temp *= k;
                temp %= MODULE;
            }
            
            sum *=temp;
            sum %= MODULE;
        }
 
        printf("%d\n", (int)sum);
    }
    return 0;
}
Добавлено через 2 минуты
Придется подключать длинную арифметику, можно считать в дабле, но там нет операции деления по модулю.
В задаче предел верхний 500!/(490!(10!)) = 245810588801891098700, 26 степень

Добавлено через 2 минуты
была еще задача на всесибирской олимпиаде потанина этого года, там нужно было найти в треугольнике паскаля определенную строку, умножить на соотв числа из списка, а потом чередуя знак сложить, т.е. дано 3 числа к примеру a1,a2,a3 делаем 1*a1 - 2*a2 + a3 и тд, а коэффициенты разрастались страшно, а могло быть до тысячных рядов и ответ по модулю.
препод сказал что есть способ хранить остаток в 2 числах и тогда получать норм ответ (типа хранить макс степень модуля и остаток), но мы не поняли как.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.02.2012, 07:12     деления по модулю, остатки #6
Проверяйте:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MODULE 1000000007
 
#define ord(a) (('a' <= a && 'z' >= a)? (a - 'a'):(a - 'A' + 32))
int a[11][501];
int func(int col, int l)
{
    if(col==l)
        return 1;
    if(col==1)
        return l;
    if(a[col][l])
        return a[col][l];
    int i;
    __int64 sum=0;
    for(i=0; i<=l-col; i++)
    {
        sum+=func(col-1, l-i-1);
        sum%=MODULE;
    }
    a[col][l]=(int)sum;
    return a[col][l];
 
}
int main()
{
        int T, i;
        char arr[501];
        int str[501];
        __int64 sum;
        scanf("%d", &T);
        for (i = 0; i < T; i++)
        {
                int l, j;
 
                memset(arr, 0, 501 * sizeof(char)), 
                memset(str, 0, 501 * sizeof(int));
                sum = 1;
                scanf("%s", &arr);
                l = strlen(arr);
                for (j = 0; j < l; ++j)
                        str[ord(arr[j])]++;
              
                for (j = 0; j < 90; ++j)
                {
                    if(str[j])
                    {
                        sum*=func(str[j], l);
                        sum %= MODULE;
                        l-=str[j];
                    }
                }
                printf("%d\n", (int)sum);
        }
        return 0;
}
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
04.02.2012, 09:57  [ТС]     деления по модулю, остатки #7
wrong answer, с телефона и не успел разобраться с смыслом функции. каким образом считается все?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.02.2012, 11:01     деления по модулю, остатки #8
Цитата Сообщение от AC-93 Посмотреть сообщение
wrong answer,
Ну во первых проверочная система выдавала не WA, а CE (ошибка компиляции). Я зарегистрировался на этом сайте, только для того что бы сдать задачу. Заменил в 2-х местах в моем коде __int64 на long long и задача прошла все тесты.

Цитата Сообщение от AC-93 Посмотреть сообщение
каким образом считается все?
В личку обращайтесь, объясню.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2012, 11:45     деления по модулю, остатки
Еще ссылки по теме:

Получить новую матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент C++
Заменить все положительные элементы массива на их остатки от деления на 5 C++
Получить новую матрицу путем деления всех элементов на ее наибольший по модулю элемент C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
04.02.2012, 11:45  [ТС]     деления по модулю, остатки #9
заменил тоже на лонги, сдавал как gcc C 89, попробую еще раз...

Добавлено через 3 минуты
Сдал под ++ гсс, прошло, большое спасибо, вечером рассмотрю еще раз ваш алгоритм, если так и не пойму - обращусь. Спасибо.
Yandex
Объявления
04.02.2012, 11:45     деления по модулю, остатки
Ответ Создать тему
Опции темы

Текущее время: 15:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru