洛谷绿题的存在。

有 \(T\) 组数据，根据条件判断逆序对对数。

我们用求逆序对模板来做这道题，但是树状数组里面存的是质因数。剩下的一模一样，有点卡常，代码有点难写，故评绿。

std & 参考代码：

#include <iostream>
#include <vector> 
#include <cstdio>
#define endl '\n'
using namespace std;

__always_inline int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch<'0'&&ch>'9'){
        if(ch=='-') f = 0-f;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = x*10+(ch-'0');
        ch = getchar();
    }
    return x*f;
}
long long c[10000005];
int a[10000005];
int n;
int maxn = -1;
vector<int> primes;
bool she[10000005];
__always_inline void primes_sieve(){
    she[1] = she[0] = true;
    for(int i = 2;i<=1000000;i++){
        if(!she[i]){
            primes.push_back(i);
        }
        for(auto it:primes){
            if(it*i>10000000) break;
            she[it*i] = true;
            if(i%it==0) break;
        } 
    }
}
__always_inline int lowbit(int i){
    return i&(-i);
}
__always_inline void add(int id,int val){
    for(int i = id;i<=primes[primes.size()-1];i+=lowbit(i)) c[i]+=val;
}
__always_inline long long query(int l,int r){
    long long ans = 0;
    for(int i = r;i;i-=lowbit(i)) ans+=c[i];
    for(int i = l-1;i;i-=lowbit(i)) ans-=c[i];
    return ans; 
}
signed main()
{
    // freopen("nixudui10.in","rb",stdin);
    // freopen("nixudui10.out","wb",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    _ = read();
    primes_sieve();
//  cout<<she[8]<<endl;
    while(_--){
        maxn = -1;
        n = read();
        for(int i = 1;i<=n;i++){
            a[i] = read();
            maxn = max(maxn,a[i]);
        }
        for(int i = 1;i<=maxn;i++){
            c[i] = 0;
        }
        long long ans = 0;
        for(int i = 1;i<=n;i++){
            for(auto it:primes){
                if(it>a[i]) break;
                if(a[i]%it==0){//求逆序对对数
                    ans+=query(it+1,maxn);
//                  cout<<it<<' ';
                }
//              add(it+1,-1);
//          cout<<ans<<' ';
            }
//          cout<<endl;
            for(auto it:primes){//加进树状数组里面
                if(it>a[i]) break;
                if(a[i]%it==0) add(it,1);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}