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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
AC-93
16 / 16 / 0
Регистрация: 27.01.2010
Сообщений: 150
#1

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

03.02.2012, 18:49. Просмотров 1752. Ответов 8
Метки нет (Все метки)

для олимпиад часто нужно и до конца не могу разобраться. кто знает продвинутые источники по этой теме, особенно когда 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++):

Заменить все положительные элементы массива на их остатки от деления на 5 - C++
Дан массив из 30-ти элементов. Написать программу, которая заменит все положительные элементы массива на их остатки от деления на 5, а...

Найти х если известны остатки от деления этого числа на 3, 5, 7 - C++
3. Задумано некоторое число х (х <100). Известны числа k, т, п - остатки от деления этого числа на 3, 5, 7. Найти х.

Распечатать все числа от 1 до N, у которых остатки от деления на число Z не превышают числа M. - C++
1. Распечатать все числа от 1 до N, у которых остатки от деления на число Z не превышают числа M. Помогите написать((

Распечатать все числа от 1 до N, у которых остатки от деления на число Z не превышают числа M - C++
Распечатать все числа от 1 до N, у которых остатки от деления на число Z не превышают числа M. #include <iostream> using namespace std;...

Получить новую матрицу путем деления всех элементов на ее наибольший по модулю элемент - C++
Помогите написать программу на c++, задание: Дана действительная матрица размера n×m , в которой не все элементы равны нулю. Получить...

Получить матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент - C++
Задание: написать программу согласно заданию. Дана целочисленная матрица размера 5х5. Получить новую матрицу путем деления всех...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
03.02.2012, 18:54 #2
дайте ссылку на задачу
AC-93
16 / 16 / 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++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.02.2012, 21:18 #4
Цитата Сообщение от AC-93 Посмотреть сообщение
в общем мне нужно как-то преобразовать начальное, чтобы можно было брать остаток у а, т.к. оно большое и без модуля не влезает никуда.
Что бы можно было брать остаток у a и в то же время невозможно a/b - так не бывает. Для Вашей задачи используйте __int64, и все получится.
Если покажете Ваше решение, то помогут быстрее.
AC-93
16 / 16 / 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++
4670 / 2496 / 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
16 / 16 / 0
Регистрация: 27.01.2010
Сообщений: 150
04.02.2012, 09:57  [ТС] #7
wrong answer, с телефона и не успел разобраться с смыслом функции. каким образом считается все?
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.02.2012, 11:01 #8
Цитата Сообщение от AC-93 Посмотреть сообщение
wrong answer,
Ну во первых проверочная система выдавала не WA, а CE (ошибка компиляции). Я зарегистрировался на этом сайте, только для того что бы сдать задачу. Заменил в 2-х местах в моем коде __int64 на long long и задача прошла все тесты.

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

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

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

Получить новую матрицу путём деления всех элементов заданной матрицы на наибольший по модулю элемент - C++
знаю что уже много где написано про это, но никак не могу докрутить. есть такой код. а задание таково Заполнить матрицу А размера ,...

Получить новую матрицу путем деления всех элементов исходной матрицы на ее наибольший по модулю элемент - C++
2)Задан двумерный массив А. Получить новую матрицу путем деления всех элементов исходной матрицы на ее наибольший по модулю элемент.

Получить новую матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент - C++
помогите с задачей,надо написать код на с++ Дана действительная матрица размером m×n, в которой не все элементы равны нулю. Получить...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
04.02.2012, 11:45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru