CF1899D Yarik and Musical Notes

思路

暴力化简公式题。

假定 $b_{i}^{b_j} = b_{j}^{b_{i}}$ 成立，那么有：

$$2^{a_i \times 2^{a_j}} = 2^{a_j \times 2^{a_i}}\\ a_i \times 2^{a_j} = a_j \times 2^{a_i}\\ \frac{a_i}{a_j} = \frac{2^{a_i}}{2^{a_j}}\\ \frac{a_i}{a_j} = 2^{a_i - a_j}$$

因为 $\frac{a_i}{a_j} = 2^{a_i - a_j}$ 成立，所以 $a_i,a_j$ 除了 $2$ 以外的所有质因子数量相同，不妨令 $t_i$ 表示 $a_i$ 中 $2$ 这个质因子出现的次数。那么有：

$$2^{t_i - t_j} = 2^{a_i - a_j}\\ t_i - t_j = a_i - a_j\\ a_i - t_i = a_j - t_j$$

所以直接用 map 维护一下所有 $a_i - t_i$ 的值，然后根据加法原理全部加起来即可。

注意在代码实现的时候，要在 map 中加上一维，表示 $\frac{a_i}{2^{t_i}}$，因为在证明中假定了条件成立，但是在实现中，需要加上 $a_i$ 与 $a_j$ 除 $2$ 外的质因子数量不同的情况。

Code

#include <bits/stdc++.h>  
#define fst first  
#define snd second  
#define re register  
#define int long long  
  
using namespace std;  
  
typedef pair<int,int> pii;  
const int N = 2e5 + 10;  
int T,n;  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline void solve(){  
    int ans = 0;  
    map<pii,int> vis;  
    n = read();  
    for (re int i = 1;i <= n;i++){  
        int x,t,num = 0;  
        x = t = read();  
        while (t % 2 == 0){  
            num++;  
            t >>= 1;  
        }  
        vis[{t,x - num}]++;  
    }  
    for (auto it = vis.begin();it != vis.end();it++){  
        int cnt = it -> second;  
        ans += cnt * (cnt -  1) / 2;  
    }  
    printf("%lld\n",ans);  
}  
  
signed main(){  
    T = read();  
    while (T--) solve();  
    return 0;  
}