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

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