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 [ ]:
Content source: nicalvarez/e-maxx.es
Similar notebooks: