In [15]:
import urllib2
from scrapy.selector import Selector
from scrapy.http import HtmlResponse

In [16]:
xpath = '//table/tbody/tr[2]/td[2]/textarea'
url = 'http://e-maxx.ru/algo/src_euler_function'

In [74]:
r = urllib2.urlopen(url)
body = r.read()
body = unicode(body, errors='replace')
ext = Selector(text=body).xpath('//textarea/text()').extract()

In [77]:
print ext[0]


\h1{ ������� ������ }


\h2{ ����������� }

\bf{������� ������} $\phi (n)$ (������ ������������ $\varphi(n)$ ��� ${\it phi}(n)$) --- ��� ���������� ����� �� $1$ �� $n$, ������� ������� � $n$. ����� �������, ��� ���������� ����� ����� � ������� $[1; n]$, \algohref=euclid_algorithm{���������� ����� ��������} ������� � $n$ ����� �������.

��������� ������ �������� ���� ������� (\href=http://oeis.org/A000010{A000010 � ������������ OEIS}):

$$ \phi (1)=1, $$
$$ \phi (2)=1, $$
$$ \phi (3)=2, $$
$$ \phi (4)=2, $$
$$ \phi (5)=4. $$


\h2{ �������� }

��� ��������� ������� �������� ������� ������ --- ����������, ����� ��������� ��������� �� ��� ����� �����:

\ul{

\li ���� $p$ --- ������� �����, �� $\phi (p)=p-1$.

(��� ��������, �.�. ����� �����, ����� ������ $p$, ������� ������ � ���.)

\li ���� $p$ --- �������, $a$ --- ����������� �����, �� $\phi (p^a)=p^a-p^{a-1}$.

(��������� � ������ $p^a$ �� ������� ������ ������ ����� ���� $pk$ $(k \in \mathcal{N})$, ������� $p^a / p = p^{a-1}$ ����.)

\li ���� $a$ � $b$ ������� �������, �� $\phi(ab) = \phi(a) \phi(b)$ ("�������������������" ������� ������).

(���� ���� ������� �� \algohref=chinese_theorem{��������� ������� �� ��������}. ���������� ������������ ����� $z \le ab$. ��������� ����� $x$ � $y$ ������� �� ������� $z$ �� $a$ � $b$ ��������������. ����� $z$ ������� ������ � $ab$ ����� � ������ �����, ����� $z$ ������� ������ � $a$ � � $b$ �� �����������, ���, ��� �� �� �����, $x$ ������� ������ � $a$ � $y$ ������� ������ � $b$. �������� ��������� ������� �� ��������, ��������, ��� ����� ���� ����� $x$ � $y$ $(x \le a, ~ y \le b)$ ������� ���������� ������������� ����� $z$ $(z \le ab)$, ��� � ��������� ��������������.)

}

������ ����� �������� ������� ������ ��� ������ $\it n$ ����� ��� \bf{������������} (���������� $n$ �� ������� �����������):

����

$$ n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k} $$

(��� ��� $p_i$ --- �������), ��

$$ \phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdot \ldots \cdot \phi(p_k^{a_k}) = $$
$$ = (p_1^{a_1} - p_1^{a_1-1}) \cdot (p_2^{a_2} - p_2^{a_2-1}) \cdot \ldots \cdot (p_k^{a_k} - p_k^{a_k-1}) = $$
$$ = n \cdot \left( 1-{1\over p_1} \right) \cdot \left( 1-{1\over p_2} \right) \cdot \ldots \cdot \left( 1-{1\over p_k} \right). $$


\h2{ ���������� }

���������� ���, ����������� ������� ������, ���������� ����� ������������ ������� �� $O (\sqrt n)$:

\code
int phi (int n) {
	int result = n;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			result -= result / i;
		}
	if (n > 1)
		result -= result / n;
	return result;
}
\endcode

�������� ����� ��� ���������� ������� ������ --- ��� ���������� \bf{������������} ����� $n$. ��� ����� ����������� �� �����, ����������� ������� $O(\sqrt{n})$: ��. \algohref=factorization{����������� ��������� ������������}.


\h2{ ���������� ������� ������ }

����� ��������� � ������ �������� ������� ������ ���������� � \bf{������� ������}:
$$ a^{\phi(m)} \equiv 1 \pmod m, $$
��� $\it a$ � $\it m$ ������� ������.

� ������� ������, ����� $\it m$ �������, ������� ������ ������������ � ��� ���������� \bf{����� ������� �����}:
$$ a^{m-1} \equiv 1  \pmod m $$

������� ������ ���������� ����� ����������� � ������������ �����������, ��������, ��. \algohref=reverse_element{�������� ������� � ���� �� ������}.


\h2{ ������ � online judges }

������ �����, � ������� ��������� ��������� ������� ������,���� ��������������� �������� ������, ���� �� �������� ������� ������ ��������������� �������� �����:

\ul{

\li \href=http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1120{UVA #10179 \bf{"Irreducible Basic Fractions"} ~~~~ [���������: ������]}

\li \href=http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1240{UVA #10299 \bf{"Relatives"} ~~~~ [���������: ������]}

\li \href=http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302{UVA #11327 \bf{"Enumerating Rational Numbers"} ~~~~ [���������: �������]}

\li \href=http://acm.timus.ru/problem.aspx?space=1&num=1673{TIMUS #1673 \bf{"������ � ��������"} ~~~~ [���������: �������]}

}

In [36]:
_, params = cgi.parse_header(r.headers.get('Content-Type', ''))
encoding = params.get('charset', 'unicode')
text = r.read().decode(encoding)
print url


---------------------------------------------------------------------------
LookupError                               Traceback (most recent call last)
<ipython-input-36-9e41dd3f32ad> in <module>()
      1 _, params = cgi.parse_header(r.headers.get('Content-Type', ''))
      2 encoding = params.get('charset', 'unicode')
----> 3 text = r.read().decode(encoding)
      4 print url

LookupError: unknown encoding: unicode

In [ ]: