1. Си / Говнокод #24350

    −1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    int mysolve (int a, int b, int m) {
    	int n = (int) sqrt (m + .0) + 1;
     
    	int an = 1;
    	for (int i = n, t = a; i;) {
    		if (i & 1) {
    		    an = (an * t) % m;
    		    i -= 1;
    		} else {
    			t = (t * t) % m;
    			i >>= 1;
    		}
            }
     
    	int *vals = (int*) malloc(m * sizeof(int));
    	memset(vals, -1, m * sizeof(int));
     
    	for (int i = 1, cur = an; i <= n; ++i) {
    		if (vals[cur] == -1) vals[cur] = i;
    		cur = (cur * an) % m;
    	} 
     
    	for (int i = 0, cur = b; i <= n; ++i) {
    		if (vals[cur] != -1) {
    			int ans = vals[cur] * n - i;
    			if (ans < m) {
    				free(vals);
    				return ans;
    			}
    		}
    		cur = (cur * a) % m;
    	}
    	free(vals);
    	return -1;
    }

    Чото както тухло тут.
    Вот держите, вспомнил своё олимпиАДное прошлое, перевёл на Сишку и оптимизировал вот этоу хуйнц: https://e-maxx.ru/algo/discrete_log
    Чем больше модуль, ьем боьше жрёт память, дальше оптимизировать лень.

    Мне кажется, что что-то я здесь сделал не так...

    Запостил: 666_N33D135, 02 Июня 2018

    Комментарии (25) RSS

    • Вкусно?

      Здесь, кстати есть ошипка, но непонятно где.
      Ответить
    • Вот здесь без ашипки, но немного по-другому:
      int mysolve (int a, int b, int m) {
      	int n = (int) sqrt (m + .0) + 1;
       
      	int an = 1;
      	for (int i = n, t = a; i;) {
      		if (i & 1) {
      		    an = (an * t) % m;
      		    i -= 1;
      		} else {
      			t = (t * t) % m;
      			i >>= 1;
      		}
          }
       
      	int *vals = (int*) malloc(n * sizeof(int));
       
      	for (int i = 0, cur = an; i < n; ++i) {
      		vals[i] = cur;
      		cur = (cur * an) % m;
      	}
       
      	for (int i = 0, cur = b; i <= n; ++i) {
      		int j;
      		for (j = 0; j < n && vals[j] != cur; ++j)
      		    ;
      		if (j < n) {
      			int ans = (j + 1) * n - i;
      			if (ans < m) {
      				free(vals);
      				return ans;
      			}
      		}
      		cur = (cur * a) % m;
      	}
      	free(vals);
      	return -1;
      }
      Ответить
      • @
        for (j = 0; j < n && vals[j] != cur; ++j)
        ;


        Надо же. Я думал, что только в Delphi такое оператороблядство.
        Ответить
    • Приятный синтаксис. Это чистый С?
      Ответить
      • Да, безо всяких нестандартных расширений, без забытых малоиспользуемых элементов синтаксиса. Это как Simple English или Basic English.
        Ответить
        • Разве можно писать for(int i =...?
          Ответить
          • Проморгал... В старой сишке было нельзя. В C99 уже можно. Так что это уже новый диалект.
            Ответить
            • Хм. Нам препод писал что "си" не поддерживает объявление переменных в цикле, и было это гораздо позже 99...
              Ответить
              • Мне это буквально в этом году говорили.
                Ответить
              • Он, наверное, про C89 говорил
                Ответить
                • Мы "си" проходили мельком. Могу предположить, что этот конспект он написал еще до 99 года.
                  Ответить
          • Я, кстати, ещё где-то год назад так не писал — C++ ная привычка, я так стал писать на лабах, чтобы по-быстрому хуяк-хуяк, сделал лабу и свалил.
            Ответить
      • Нет, с примесью С99, не так торкает.
        Ответить
        • Дух старой школы живёт только в K&R!
          int mysolve(a, b, m)
              int a;
              int b;
              int m;
              {
          	int n = (int) sqrt (m + .0) + 1;
           
          	int an = 1;
                  int n;
          	for (i = n, t = a; i;) {


          Ещё можно тип результата как int не объявлять, сишка его выведет автоматически...
          Ответить
          • P.S. Хотел написать int i, а написал int n.
            Ответить
          • > int не объявлять, сишка его выведет автоматически...

            Это, кстати, в C99 убрали.
            Ответить
          • Почему m подсветилось?
            Ответить
            • Он почему-то как perl это запостил. А в пёрле m — херня для регулярок.
              Ответить
              • Да в пёрле почти всё — херня для регулярок.
                Ответить
            • Потому что highlight.js решил, что это перл (видно в инспекторе).
              Ответить

    Добавить комментарий