given an array consists of $$$n$$$ integers and an integer $$$p$$$, find number of pair($$$i,j$$$):
so that $$$i<j$$$ and $$$(a[i]*a[j])$$$ $$$mod$$$ $$$p$$$ $$$=$$$ $$$(a[i]+a[j])$$$ $$$mod$$$ $$$p$$$
$$$n<=10^5$$$
$$$1<p<=10^9$$$
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
given an array consists of $$$n$$$ integers and an integer $$$p$$$, find number of pair($$$i,j$$$):
so that $$$i<j$$$ and $$$(a[i]*a[j])$$$ $$$mod$$$ $$$p$$$ $$$=$$$ $$$(a[i]+a[j])$$$ $$$mod$$$ $$$p$$$
$$$n<=10^5$$$
$$$1<p<=10^9$$$
Название |
---|
Im not sure if this really works, but this is what I thought: rearranging the expression, we have $$$a_i \cdot a_j - (a_i+a_j) \equiv 0 \mod{p}$$$, which is equivalent to $$$(a_i-1)(a_j-1) \equiv 1 \mod{p}.$$$ This implies that $$$a_i \equiv a_j \equiv 0$$$ or $$$2 \mod{p}$$$. Then, let $$$x$$$ be the number of $$$a_k$$$ such that $$$a_k \equiv 0 \mod{p}$$$ and $$$y$$$ the number of $$$a_l$$$ such that $$$a_l \equiv 2 \mod{p}$$$. Answer is $$${x \choose 2} + {y \choose 2}$$$.
actually, this is not correct. You can pair every $$$a_i$$$ with any $$$a_j \equiv (a_i-1)^{-1}+1 \mod{p}$$$.
please give the problem link
http://online.vku.udn.vn/problem/tongtich
you can translate it into english