标签：frac int 题解 Notes times vis read Musical define

思路

暴力化简公式题。

假定 \(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;
}

标签：frac,int,题解,Notes,times,vis,read,Musical,define
From： https://www.cnblogs.com/WaterSun/p/CF1899D.html