Waterloo 2017 Winter E - Vera and Love Triangles

View as PDF

Submit solution

All submissions

Best submissions

Points: 25

Time limit: 1.0s

Memory limit: 256M

Author:

azneye

Problem types

2017 Winter Waterloo Local ACM Contest, Problem E

Vera has $N$ ~N~ friends numbered from $0$ ~0~ to $N-1$ ~N-1~. Being in Software Engineering, all her friends do not have enough spare time to engage in relationships. However, friends have crushes on each other.

If $x$ ~x~ is a non-negative integer, let $g(x)$ ~g(x)~ be the number of ones in the binary representation of $x$ ~x~.

Let $f(i,j) = g((A \cdot B^{i \cdot N + j}) \mathbin{\%} M)$ , where $A,B,M$ ~A,B,M~ are integer constants.

It is known that for any 2 friends $i$ ~i~ and $j$ ~j~ where $i < j$ ~i < j~, if $f(i,j)$ ~f(i,j)~ is even then $i$ ~i~ has a crush on $j$ ~j~, otherwise $j$ ~j~ has a crush on $i$ ~i~.

Vera thinks love triangles are very funny. A love triangle is a set of 3 friends $i,j,k$ ~i,j,k~ such that $i$ ~i~ has a crush on $j$ ~j~, $j$ ~j~ has a crush on $k$ ~k~ and $k$ ~k~ has a crush on $i$ ~i~.

Given integers $N,M,A,B$ ~N,M,A,B~ tell Vera how many love triangles exist among her friends. Two love triangles are different if they contain a different set of $3$ ~3~ friends.

Constraints

$3 \le N, M \le 200\,000$ ~3 \le N, M \le 200\,000~
$0 < A,B < M$ ~0 < A,B < M~
$N,M,A,B$ ~N,M,A,B~ are integers
$M$ ~M~ is prime

Input Specification

The input will be in the format:

$N$ ~N~ $M$ ~M~ $A$ ~A~ $B$ ~B~

Output Specification

Output one line with the number of love triangles.

Sample Input 1

3 5 3 4

Sample Output 1

Explanation of Sample Output 1

Let $a \to b$ ~a \to b~ denote that friend $a$ ~a~ has a crush on friend $b$ ~b~.

We have $f(0,1) = 1$ ~f(0,1) = 1~, $f(0,2)=2$ ~f(0,2)=2~, and $f(1,2)=1$ ~f(1,2)=1~. So $0 \to 2$ ~0 \to 2~, $2 \to 1$ ~2 \to 1~, and $1 \to 0$ ~1 \to 0~, so there is one love triangle.