Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

TuHoangAnh's blog

need help with this problem
By TuHoangAnh, history, 5 years ago, In English

given an array consists of $$$n$$$ integers and an integer $$$p$$$, find number of pair($$$i,j$$$):

so that $$$i \lt j$$$ and $$$(a[i]*a[j])$$$ $$$mod$$$ $$$p$$$ $$$=$$$ $$$(a[i]+a[j])$$$ $$$mod$$$ $$$p$$$

$$$n \lt =10^5$$$

$$$1 \lt p \lt =10^9$$$

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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}$$$.

→ Reply
  • »
    »
    5 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    actually, this is not correct. You can pair every $$$a_i$$$ with any $$$a_j \equiv (a_i-1)^{-1}+1 \mod{p}$$$.

    → Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

please give the problem link

→ Reply