Hello everyone this is my first time posting, so please bare with me :P↵
↵
So I was solving this [problem](https://mirror.codeforces.com/problemset/problem/1931/D) and came up with a solution.↵
↵
**Idea** — ↵
↵
say for example x = 7. if _ai_ is of the form _7d + 2_ then _aj_ needs to be of the form _7q + '5'_. Basically the remainders of _ai % x_ and _aj % x_ needs to add up to x for the sum to be divisible by x.↵
also for _ai — aj_ to be divisible by y, ai % y must be same as aj % y.↵
↵
Initialize a 2d vector(rems) with all values set to 0.↵
↵
Loop through the input vector and calculate _input%y(remy)_ and _input%x(remx)_↵
increment _rems[remy][remx]_.↵
↵
calculate all possibilities by multiplying _rems[remy][remx] * rems[remx][x-remx]_ at every iteration and add that to _ans_ variable.↵
also subtract the result of product of last time when we iterated through the same rems[remy][remx].↵
↵
if say x = 8 and remx = 4;↵
the we have to select combinations of 2 elements↵
so we do _Nc2_ for such values.↵
↵
~~~~~↵
long long n,x,y;↵
cin >> n >> x >> y;↵
vector<vector<long long>> v(n);↵
for(int i = 1;i < n; ++i) cin >> v[i];↵
↵
vector<vector<long long>> rems(y, vector<long long> (x, 0)); //init a 2d array↵
ll ans = 0;↵
ll remx,remy;↵
ll curr,curr2;↵
↵
for(int i = 0; i < n;++i){↵
remy = v[i]%y;↵
remx = v[i]%x;↵
rems[remy][remx]++;↵
curr = rems[remy][remx]; ↵
if(remx && remx!= (x- remx)){↵
curr2 = rems[remy][x-remx];↵
ans += (curr * curr2) - ((curr - 1) * (curr2)); // on simplification = curr2↵
}↵
else{↵
ans+= (curr * (curr - 1))/2 - ((curr - 1) * (curr -2)/2); //Nc2 - (N-1)C2↵
}↵
}↵
↵
cout << ans << '\n'; ↵
~~~~~↵
I am unable to identify where am I going wrong? Exactly where is it taking so long?↵
Specifically it gives TLE on test case 3.↵
Also I don't wanna spoil the solution to me by reading tutorial.↵
↵
If I'm unclear in any part of solution please do let me know. I'll try my best to explain again.↵
Thanks!↵
↵
So I was solving this [problem](https://mirror.codeforces.com/problemset/problem/1931/D) and came up with a solution.↵
↵
**Idea** — ↵
↵
say for example x = 7. if _ai_ is of the form _7d + 2_ then _aj_ needs to be of the form _7q + '5'_. Basically the remainders of _ai % x_ and _aj % x_ needs to add up to x for the sum to be divisible by x.↵
also for _ai — aj_ to be divisible by y, ai % y must be same as aj % y.↵
↵
Initialize a 2d vector(rems) with all values set to 0.↵
↵
Loop through the input vector and calculate _input%y(remy)_ and _input%x(remx)_↵
increment _rems[remy][remx]_.↵
↵
calculate all possibilities by multiplying _rems[remy][remx] * rems[remx][x-remx]_ at every iteration and add that to _ans_ variable.↵
also subtract the result of product of last time when we iterated through the same rems[remy][remx].↵
↵
if say x = 8 and remx = 4;↵
the we have to select combinations of 2 elements↵
so we do _Nc2_ for such values.↵
↵
~~~~~↵
long long n,x,y;↵
cin >> n >> x >> y;↵
vector<vector<long long>> v(n);↵
for(int i = 1;i < n; ++i) cin >> v[i];↵
↵
vector<vector<long long>> rems(y, vector<long long> (x, 0)); //init a 2d array↵
ll ans = 0;↵
ll remx,remy;↵
ll curr,curr2;↵
↵
for(int i = 0; i < n;++i){↵
remy = v[i]%y;↵
remx = v[i]%x;↵
rems[remy][remx]++;↵
curr = rems[remy][remx]; ↵
if(remx && remx!= (x- remx)){↵
curr2 = rems[remy][x-remx];↵
ans += (curr * curr2) - ((curr - 1) * (curr2)); // on simplification = curr2↵
}↵
else{↵
ans+= (curr * (curr - 1))/2 - ((curr - 1) * (curr -2)/2); //Nc2 - (N-1)C2↵
}↵
}↵
↵
cout << ans << '\n'; ↵
~~~~~↵
I am unable to identify where am I going wrong? Exactly where is it taking so long?↵
Specifically it gives TLE on test case 3.↵
Also I don't wanna spoil the solution to me by reading tutorial.↵
↵
If I'm unclear in any part of solution please do let me know. I'll try my best to explain again.↵
Thanks!↵
