Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%

@yutr777 · Регистрация: 07.04.2013

Author24 — интернет-сервис помощи студентам

≡ вот эта закарюка меня пугает,подскажите, что это?
и решите пожалуйста задачку
Требуется для заданных K N M и X найти количество пар чисел A и B таких, что A≡0 (mod N), B≡0 (mod M), 0≤A,B<2 K , A⊕B=X.

Формат входных данных

Первая строка содержит целые числа K N M и X (1≤K≤30, 1≤N,M,X≤2×10(в девятой)9 ).

Формат результата

Выведите искомое количество пар чисел.

Примеры

Входные данные Результат работы
3 1 2 5
4
Примечания

Искомые пары (1;4), (3;6), (5;0) и (7;2).

@ya_noob · 10.04.2013, 19:25

Сообщение от yutr777

≡ вот эта закарюка меня пугает,подскажите, что это?

читается как "тождественно равно"

@yutr777 · 10.04.2013, 19:36 **[ТС]**

Сообщение от ya_noob

читается как "тождественно равно"

а что оно обозначает?

@abit · 10.04.2013, 19:45

эта запись A≡0 (mod N) означает, что A делится на N без остатка (т.е. A должно быть кратно N)

собстна как найти количество пар мне в голову приходит только решение в лоб - сделать вложенный цикл по A и B в котором написать

C++

1	if((A^B)==X) ++paircounter;

но может есть и более оптимальное решение, надо полистать комбинаторику и теорию чисел

собстна я бы написал вам решение в лоб, но что-то у вас в условии не сходится

тут

0≤A,B<2 K

сказано чётко, что A и B должны быть строго меньше 2K насолько я вижу
а ваши две пары из примера противоречат условию
(3;6) и (7;2)
в первом случае B=6=2*K (не меньше)
во втором случае A=7>2*K (больше)

проверьте условие

@yutr777 · 10.04.2013, 19:52 **[ТС]**

Сообщение от abit

эта запись A≡0 (mod N) означает, что A делится на N без остатка (т.е. A должно быть кратно N)

собстна как найти количество пар мне в голову приходит только решение в лоб - сделать вложенный цикл по A и B в котором написать

C++

1	if((A^B)==X) ++paircounter;

но может есть и более оптимальное решение, надо полистать комбинаторику и теорию чисел

собстна я бы написал вам решение в лоб, но что-то у вас в условии не сходится

тут

сказано чётко, что A и B должны быть строго меньше 2K насолько я вижу
а ваши две пары из примера противоречат условию
(3;6) и (7;2)
в первом случае B=6=2*K (не меньше)
во втором случае A=7>2*K (больше)

проверьте условие

условие верное...некоторые команды сдали эту задачу...я никак не могу(

@abit · 10.04.2013, 20:00

а, дошло)

вот в общем решение в лоб

C++

# include <iostream>
 
int main()
{
    unsigned int paircounter=0;
    unsigned int K,N,M,X;
    
    std::cin >> K >> N >> M >> X;
    
    for(unsigned int A = 0; A!=2*K; ++A)
     for (unsigned int B = 0; B!=2*K; ++B)
     if(((A^B)==X)&&(A%N==0)&&(B%N==0)) ++paircounter;          
    std::cout <<paircounter<<std::endl;;
    return 0;
 
}

Добавлено через 5 минут
все же искомые пары не те, что вы указали а
(0;5),(1;4),(4;1) и (5;0)

так и передайте составителям задач

@yutr777 · 10.04.2013, 20:01 **[ТС]**

Сообщение от abit

эта запись A≡0 (mod N) означает, что A делится на N без остатка (т.е. A должно быть кратно N)

собстна как найти количество пар мне в голову приходит только решение в лоб - сделать вложенный цикл по A и B в котором написать

C++

1	if((A^B)==X) ++paircounter;

но может есть и более оптимальное решение, надо полистать комбинаторику и теорию чисел

собстна я бы написал вам решение в лоб, но что-то у вас в условии не сходится

тут

сказано чётко, что A и B должны быть строго меньше 2K насолько я вижу
а ваши две пары из примера противоречат условию
(3;6) и (7;2)
в первом случае B=6=2*K (не меньше)
во втором случае A=7>2*K (больше)

проверьте условие

я задал вопрос...это два в К-ой степени

@Ternsip · 10.04.2013, 20:03

yutr777, задача чрезвычайно простая, особенно, учитывая что k <= 30. Вот, если n,m,K < 10^18 уже другое дело

@yutr777 · 10.04.2013, 20:04 **[ТС]**

Сообщение от Ternsip

yutr777, задача чрезвычайно простая, особенно, учитывая что k <= 30. Вот, если n,m,K < 10^18 уже другое дело

решите пожалуйста, умоляю вас....я бы даже на колени стал...очень важно, чтобы вы помогли...Спасибо!

@Ternsip · 10.04.2013, 20:07

yutr777, для вашей задачи abit уже написал решение

@yutr777 · 10.04.2013, 20:08 **[ТС]**

Сообщение от Ternsip

yutr777, для вашей задачи abit уже написал решение

но там не 2*k а 2^k

@abit · 10.04.2013, 20:15

Сообщение от yutr777

но там не 2*k а 2^k

C++

# include <iostream>
 
int main()
{
    unsigned int paircounter=0;
    unsigned int K,N,M,X;
    
    std::cin >> K >> N >> M >> X;
    
    for(unsigned int A = 0; A!=2<<(K-1); ++A)
     for (unsigned int B = 0; B!=2<<(K-1); ++B)
     if(((A^B)==X)&&(A%N==0)&&(B%M==0)) 
        ++paircounter; 
 
    std::cout <<paircounter<<std::endl;;
    return 0;
 
}

Добавлено через 1 минуту
всё, верно... с парами тоже
так можно поглядеть на эти пары:

C++

# include <iostream>
 
int main()
{
    unsigned int paircounter=0;
    unsigned int K,N,M,X;
    
    std::cin >> K >> N >> M >> X;
    
    for(unsigned int A = 0; A!=2<<(K-1); ++A)
     for (unsigned int B = 0; B!=2<<(K-1); ++B)
     if(((A^B)==X)&&(A%N==0)&&(B%M==0)) 
      {
        std::cout <<"("<<A<< ","<<B<<")"<<std::endl;;
        ++paircounter; 
      }
    std::cout <<paircounter<<std::endl;;
    return 0;
 
}

старый мой бред не читайте) там ошибка была... не углядел, а здесь уже для 2^K

@Ternsip · 10.04.2013, 20:18

yutr777, решается она так: Заметим, что в двоичной записи числа X: в i-м разряде если стоит 0, то в числах a,b из всех пар, на данной позиции должны стоять либо 0,0 либо 1,1, если там 1 то должны стоять 1,0 либо 0,1 таким образом можно комбинаторно определить сколько всего же таких чисел. Ну раз вам это так нужно я попробую))

Добавлено через 37 секунд
abit, введите у себя k = 30

@yutr777 · 10.04.2013, 20:20 **[ТС]**

Сообщение от Ternsip

yutr777, решается она так: Заметим, что в двоичной записи числа X: в i-м разряде если стоит 0, то в числах a,b из всех пар, на данной позиции должны стоять либо 0,0 либо 1,1, если там 1 то должны стоять 1,0 либо 0,1 таким образом можно комбинаторно определить сколько всего же таких чисел. Ну раз вам это так нужно я попробую))

Добавлено через 37 секунд
abit, введите у себя k = 30

спасибо)
просто это действительно вопрос жизни и смерти

@abit · 10.04.2013, 20:25

Сообщение от Ternsip

Добавлено через 37 секунд
abit, введите у себя k = 30

ну я предупреждал, что это влоб... работать будет, но медленно
если это олимпиадная задача - то там есть ограничения на время и так делать не стоит
конечно предпочтительнее комбинаторику влепить, но тогда мне не совсем понятно как получить сами пары чисел, ну в общем как сделаете, погляжу )

@Ternsip · 10.04.2013, 20:30

yutr777, понимаете, в таком случае задача действительно сложная и требует некоторое время для решения.
Но сложность её начинается вот откуда: После того, как мы заметим, что если у нас для каждого разряда X найдётся всего 2 варианта разряда в таких парах, то логично, что всего у нас таких чисел 2^(длина x в двоичной системе), но это без учёта следующих факторов: мы не отбросили числа с лидирующими нулями и не отбросили числа, которые кратны n и m и это и есть проблема.

Добавлено через 3 минуты
я там подправил

@yutr777 · 10.04.2013, 20:36 **[ТС]**

Сообщение от Ternsip

yutr777, понимаете, в таком случае задача действительно сложная и требует некоторое время для решения.
Но сложность её начинается вот откуда: После того, как мы заметим, что если у нас для каждого разряда X найдётся всего 2 варианта разряда в таких парах, то логично, что всего у нас таких чисел 2^n, но это без учёта следующих факторов: мы не отбросили числа с лидирующими нулями и не отбросили числа, которые больше n и m и это и есть проблема.

можно немного поточнее объяснить вот про пары чисел,т.е. я перевожу в двоичную систему дальше смотрю что стоит на i-ом месте(что такое i?), если 0,0 и там и там то Ок идем дальше....если 1,1 я не понял(((
вообщем чуть чуть больше объясните или примерчик киньте)

Добавлено через 4 минуты
просто я до конца не могу понять, что именно и как нужно считать

@nonedark2008 · 10.04.2013, 20:38

Первое упрощение: Из сравнимости по модулю следует, что A = k1*N B=k2*M. Так что скакать можем с шагом N и M. Второе:

Сообщение от yutr777

A⊕B=X

Точно не уверен, но мне почему-то кажется, что если нам известны A и X, то мы можем вычислить B. И наверно будет так: B = A⊕X, т.е. нам достаточно скакать тока по A, а B вычислять по формуле. А далее проверяем B % M == 0. Как-то так, больше не придумал >_>

@Ternsip · 10.04.2013, 20:40

yutr777, Как видно на картинке, если нет ограничений (A mod N) == 0 и (B mod M) == 0 и A < 2^k и И B < 2^K что 2^(длина x в двоичной системе) и есть ответ

@nonedark2008 · 10.04.2013, 20:48

Будет вот так:

C++

int main( void )
{
  UINT64 K = 3, N = 1, M = 2, X = 5;
  UINT64 A, B;
 
  for (A = 0; A < 1 << K; A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      cout << '(' << A << ',' << B << ')' << endl;
  }
  system("pause");
  return 0;
}

@yutr777 8 / 8 / 3 Регистрация: 07.04.2013 Сообщений: 85
	10.04.2013, 20:08 [ТС]	11
	Сообщение от Ternsip yutr777, для вашей задачи abit уже написал решение но там не 2*k а 2^k 0

@yutr777 8 / 8 / 3 Регистрация: 07.04.2013 Сообщений: 85
	10.04.2013, 20:20 [ТС]	14
	Сообщение от Ternsip yutr777, решается она так: Заметим, что в двоичной записи числа X: в i-м разряде если стоит 0, то в числах a,b из всех пар, на данной позиции должны стоять либо 0,0 либо 1,1, если там 1 то должны стоять 1,0 либо 0,1 таким образом можно комбинаторно определить сколько всего же таких чисел. Ну раз вам это так нужно я попробую)) Добавлено через 37 секунд abit, введите у себя k = 30 спасибо) просто это действительно вопрос жизни и смерти 0

@Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	10.04.2013, 20:30	16
	yutr777, понимаете, в таком случае задача действительно сложная и требует некоторое время для решения. Но сложность её начинается вот откуда: После того, как мы заметим, что если у нас для каждого разряда X найдётся всего 2 варианта разряда в таких парах, то логично, что всего у нас таких чисел 2^(длина x в двоичной системе), но это без учёта следующих факторов: мы не отбросили числа с лидирующими нулями и не отбросили числа, которые кратны n и m и это и есть проблема. Добавлено через 3 минуты я там подправил 0

@yutr777 8 / 8 / 3 Регистрация: 07.04.2013 Сообщений: 85
	10.04.2013, 20:36 [ТС]	17
	Сообщение от Ternsip yutr777, понимаете, в таком случае задача действительно сложная и требует некоторое время для решения. Но сложность её начинается вот откуда: После того, как мы заметим, что если у нас для каждого разряда X найдётся всего 2 варианта разряда в таких парах, то логично, что всего у нас таких чисел 2^n, но это без учёта следующих факторов: мы не отбросили числа с лидирующими нулями и не отбросили числа, которые больше n и m и это и есть проблема. можно немного поточнее объяснить вот про пары чисел,т.е. я перевожу в двоичную систему дальше смотрю что стоит на i-ом месте(что такое i?), если 0,0 и там и там то Ок идем дальше....если 1,1 я не понял((( вообщем чуть чуть больше объясните или примерчик киньте) Добавлено через 4 минуты просто я до конца не могу понять, что именно и как нужно считать 0

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	10.04.2013, 19:25	2
	Сообщение от yutr777 ≡ вот эта закарюка меня пугает,подскажите, что это? читается как "тождественно равно" 0

@yutr777 8 / 8 / 3 Регистрация: 07.04.2013 Сообщений: 85
	10.04.2013, 19:36 [ТС]	3
	Сообщение от ya_noob читается как "тождественно равно" а что оно обозначает? 0

@Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	10.04.2013, 20:03	8
	yutr777, задача чрезвычайно простая, особенно, учитывая что k <= 30. Вот, если n,m,K < 10^18 уже другое дело 0

@yutr777 8 / 8 / 3 Регистрация: 07.04.2013 Сообщений: 85
	10.04.2013, 20:04 [ТС]	9
	Сообщение от Ternsip yutr777, задача чрезвычайно простая, особенно, учитывая что k <= 30. Вот, если n,m,K < 10^18 уже другое дело решите пожалуйста, умоляю вас....я бы даже на колени стал...очень важно, чтобы вы помогли...Спасибо! 0

@Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	10.04.2013, 20:07	10
	yutr777, для вашей задачи abit уже написал решение 0

@Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	10.04.2013, 20:18	13
	yutr777, решается она так: Заметим, что в двоичной записи числа X: в i-м разряде если стоит 0, то в числах a,b из всех пар, на данной позиции должны стоять либо 0,0 либо 1,1, если там 1 то должны стоять 1,0 либо 0,1 таким образом можно комбинаторно определить сколько всего же таких чисел. Ну раз вам это так нужно я попробую)) Добавлено через 37 секунд abit, введите у себя k = 30 1

@abit 390 / 365 / 111 Регистрация: 03.02.2013 Сообщений: 1,120
	10.04.2013, 20:25	15
	Сообщение от Ternsip Добавлено через 37 секунд abit, введите у себя k = 30 ну я предупреждал, что это влоб... работать будет, но медленно если это олимпиадная задача - то там есть ограничения на время и так делать не стоит конечно предпочтительнее комбинаторику влепить, но тогда мне не совсем понятно как получить сами пары чисел, ну в общем как сделаете, погляжу ) 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	10.04.2013, 20:38	18
	Первое упрощение: Из сравнимости по модулю следует, что A = k1N B=k2M. Так что скакать можем с шагом N и M. Второе: Сообщение от yutr777 A⊕B=X Точно не уверен, но мне почему-то кажется, что если нам известны A и X, то мы можем вычислить B. И наверно будет так: B = A⊕X, т.е. нам достаточно скакать тока по A, а B вычислять по формуле. А далее проверяем B % M == 0. Как-то так, больше не придумал >_> 1

@Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	10.04.2013, 20:40	19
	yutr777, Как видно на картинке, если нет ограничений (A mod N) == 0 и (B mod M) == 0 и A < 2^k и И B < 2^K что 2^(длина x в двоичной системе) и есть ответ Миниатюры 0