4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе

Задача A. Найдите все пары

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Дано простое $P$, натуральное $n$ и массив $a$ размера $n$. Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на $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. $1 <= n <= 1000, 2 <= p <= 1000$. Оценивается в $20$ баллов.
2. $1 <= n <= 1000, p = 2$. Оценивается в $20$ баллов.
3. $1 <= n <= 100000, 2 <= p <= 1000$. Оценивается в $20$ баллов.
4. $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$}

( Nurdaulet Akhanov )

Комментарий/решение

показать/скрыть код

with open('input') as file:
    inner, data = file.readlines(), list()

    for line in range(0, len(inner)): data.append(str(inner[line]).split('\n')[0])

p, arr, sc = int(data[0].split()[1]), data[1].split(), 0

for num in range(0, int(data[0].split()[0])): 
    
    for sec in range(0, int(data[0].split()[0])):

        if num != sec:

            if (int(arr[num]) * int(arr[sec])) % p == (int(arr[num]) + int(arr[sec])) % p: sc += 1

with open('output', 'w') as file: file.write(str(sc // 2)) 

[deleted.]

[deleted.]

показать/скрыть код

#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
ll q, p, ans;
unordered_map<ll, ll> m;
ll binpow(ll n, ll k) {
  ll res = 1;
  n %= p;
  while (k > 0) {
    if (k & 1) res = (res * n) % p;
    n = (n * n) % p;
    k >>= 1;
  }
  return res;
}
ll inv(ll n) { return binpow(n, p - 2); }
int main() {
  speed;
  oprecision;
  // code
  cin >> q >> p;
  while (q--) {
    ll x;
    cin >> x;
    x = (x + p - 1) % p;
    if (!(x % p)) continue;
    ans += m[binpow(x, p - 2)];
    m[x]++;
  }
  cout << ans;
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

показать/скрыть код

n, p = map(int, input().split())
a = list(map(int, input().split()))

counter = 0

for  i in range(n-1):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % p == (a[i] * a[j]) % p:
            counter += 1

print(counter)

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair < int, int > pii;
typedef pair < pii, int > piii;
typedef pair < ll, ll > pll;
typedef pair < pll, ll > plll;
typedef pair < db, db > pdb;
typedef pair < ld, ld > pld;
typedef vector < int > vi;
typedef vector < ll > vl;
typedef vector < db > vdb;
typedef vector < ld > vld;
typedef vector < str > vstr;
typedef vector < pii > vpii;
typedef vector < pll > vpll;
typedef vector < pdb > vpdb;
typedef vector < pld > vpld;
typedef set < int > si;
typedef set < ll > sl;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define ROF(i,a,b) for(int i = (b); i >= (a); --i)
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd
#define left gsdfg
#define right aegrgs
#define tos to_string
#define nextperm next_permutation

const int N = 1e5 + 12;
const int N2 = 1e6 + 12;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;
const double eps = 1e-5;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int daym[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int base = 107;
const int hmod = 1073676287;

ll n, p, ans;
map < ll, ll > cnt;

ll mult(ll a, ll b) {
	if(a >= p) a %= p;
	if(b >= p) b %= p;
	a *= b;
	if(a >= p) a %= p;
	return a;
}

ll add(ll a, ll b) {
	if(a >= p) a %= p;
	if(b >= p) b %= p;
	a += b;
	if(a >= p) a -= p;
	return a;
}

ll binpow(ll a, ll n) {
	ll res = 1;
	while(n) {
		if(n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n >>= 1;
	}
	return res;
}

ll inv(ll a) {
	return binpow(a, p - 2);
}

void solve() {
	cin >> n >> p;
	FOR(i, 1, n) {
		ll x, A;
		cin >> x;
		x %= p;
		A = x;
		x = (x + p - 1) % p;
		if(x % p == 0) continue;
		x = mult(A, inv(x));
		ans += cnt[x];
		cnt[A]++;
	}
	cout << ans;
}

int main () {
	start
	solve();
}
/*

*/

AC

показать/скрыть код

 #include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iomanip>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define pb push_back
#define er erase
#define in insert
#define s(a, x, y) sort(a.begin() + x, a.begin() + y);
#define r(a, x, y) reverse(a.begin() + x, a.begin() + y);
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define ll long long
#define ld long double
#define forn(i, a, b) for (ll i = a; i <= b; i++)
#define form(i, a, b) for (ll i = a; i >= b; i--)
#define PI 3.14159265358979
#define INF LLONG_MAX
#define sp setprecision
#define pii pair<int, int>
#define pll pair<ll, ll>
#define gcd __gcd
#define endl '\n'
#define sz(a) (int)a.size()
#define bt(i) (1ll << (i))
#define mxu(a, b) a = max(a, b)
#define mnu(a, b) a = min(a, b)
const ll zxc = 2e5 + 13;
const int inf = 2147483647;
using namespace std;

ll binpow (ll a, ll p, ll mod){
	if (p==0) return 1;
	if (p % 2) return binpow (a, p - 1, mod) * a % mod;
	ll qwer = binpow (a, p / 2, mod);
	return qwer * qwer % mod;
}

void solve(){
    ll n, p, a[100001];
    ll cnt;
    map <ll,ll> mymap;
    map <ll,bool> used;
    cin >> n >> p;
    forn(i,0,n-1){
        cin >> a[i];
    }
    forn(i,0,n-1){
        if (a[i]%p!=0) a[i] = binpow(a[i],p-2,p);
        else a[i]=0;
    }
    forn(i,0,n-1){
        mymap[a[i]]++;
    }
    cnt = 0;
    cnt = cnt + mymap[0]*(mymap[0]-1)/2;
    forn(i,0,n-1){
        if (a[i]>=2 && !used[a[i]] && !used[p+1-a[i]]){
            if ((p+1-a[i])!=a[i]) cnt = cnt + mymap[a[i]]*mymap[p+1-a[i]];
            else cnt = cnt + mymap[a[i]]*(mymap[a[i]]-1)/2;
        }
        used[a[i]]=1;
        used[p+1-a[i]]=1;
    }
    cout << cnt;
}


int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base ::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin >> t;
    while (t--)solve();
}