4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе
Есеп A. Жұптар
Ограничение по времени:
1 second
Ограничение по памяти:
256 megabytes
Бүтін жай $P$ саны, натурал $n$ мен ұзындығы $n$ болатын $a$-массиві берілген. Егер де сандар жұбының бір-біріне көбейтіндісінің $P$-ға бөлгенінің калдығы мен сол екі санның соммасының $P$-ға бөлгенінің калдығына тең болса, осы жұп жақсы болып саналады. Ресми түрде, $x * y$ $mod$ $P = (x + y)$ $mod$ $P$ шарты орындалған жағдайда $(x, y)$ жұбы жақсы болып саналады. Массивте жақсы жұптар санын табыңыз.
Формат входного файла
Ең бірінші жолда екі бүтін сан берілген $n$ $(1 <= n <= 10^5)$ — массивтің ұзындығы, $P$ $(2 <= P <= 10^9)$ — берілген $P$ саны.
Екінші жолда $n$ сан $a_i$ $(0 <= a_i <= 10^9)$ — массивтің $i$-саны берілген.
Формат выходного файла
Бір бүтін сан шығарыңыз — жақсы жұптар саны.
Система оценки
Есеп төрт бөлімнен тұрады:
- $1 <= n <= 1000, 2 <= p <= 1000$. $20$ ұпайға есептеледі.
- $1 <= n <= 1000, p = 2$. $20$ ұпайға есептеледі.
- $1 <= n <= 100000, 2 <= p <= 1000$. $20$ ұпайға есептеледі.
- $1 <= n <= 100000, 2 <= p <= 10^9$. $40$ ұпайға есептеледі.
Примеры:
Вход 4 3 3 5 12 11Ответ
2Вход
3 5 1 2 7Ответ
1
Замечание
Жай сан — бірден үлкен, бірақ бір мен өзінен басқа сандарға бөлінбейтін, бүтін оң сан (мысалы, $2, 3, 5, 7, 11, 13, 17, \dots $).
$a$ $mod$ $b$ жазылуы, $a$-ның $b$-ға бөлгендегі қалдығын білдіреді.
- Бірінші мысалда 2 ғана жұп жақсы болып есептеледі: $(3, 12), (5, 11)$ себебі $(3 + 12)$ mod $3$ = $(3 * 12)$ mod $3$ және $(5 + 11)$ mod $3$ = $(5 * 11)$ mod $3$
- {Екінші мысалда 1 ғана жұп үйлеседі: $(2 + 7)$ mod $5$ = $(2 * 7)$ mod $5$}
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.