Problem - D - Codeforces

题目大意：给出一个n个数的数组a，问有多少对i，j满足i<j，2的a[i]次方的2的a[j]次方等于2的a[j]次方的2的a[i]次方

1<=n<=1e5;1<=a[i]<=1e9

思路：用快速幂打个表发现满足条件的a[i]，a[j]要么a[i]=a[j]要么一个数等于1，另一个等于2，所以我们只需对于每个数，求出它后面有多少与它相等的数，如果是1或2再特判一下后面2或1的数量。

那么我们就先求出每个数的出现次数，然后每遍历一个数，就令那个数的出现次数-1，这时这个数的出现次数就等于在他后面有多少个这个数

//#include<bits/stdc++.h>
#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;
ll n;
ll a[N];
ll qpow(ll a, ll b)
{//快速幂if (b <= 0)return 1;ll ret = 1, temp = a;while (b){if (b & 1){ret = ret * a % MOD;}a = a * a % MOD;b >>= 1;}return ret;
}
void init()
{}
void solve()
{cin >> n;init();map<ll, ll>cnt;for (int i = 1; i <= n; i++){cin >> a[i];cnt[a[i]]++;//求每个数的出现次数}ll ans = 0;for (int i = 1; i <= n; i++){cnt[a[i]]--;//当前数出现次数-1ans += cnt[a[i]];if (a[i] == 1){//特判1和2ans += cnt[2];}if (a[i] == 2){ans += cnt[1];}}cout << ans;cout << '\n';
}
int main()
{/*for (int i = 1; i <= 60; i++){for (int j = 1; j <= 60; j++){ll temp1 = qpow(2, i), temp2 = qpow(2, j);if (qpow(temp1, temp2) == qpow(temp2, temp1)){cout << i << " " << j << '\n';}}}*///打表找规律ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}