#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" //数学题关注边界条件和推断其他的值枚举算答案 //nlogn做法 //https://zhuanlan.zhihu.com/p/633006114 //-------------------------------------------- //因为ai*aj==bi+bj,同时对于a b数组中每个元素满足1<=ai<=n,1<=bi<=n //故由 bi+bj<=2n 推断出 ai*aj<=2n //那么就可以枚举 aj (以时间复杂度为log2(2n)) const int N=2e5+5; struct pos{ int x,y; }vec[N]; bool cmp(pos a,pos b){ return a.x<b.x; } int mp[N]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int T=1;cin>>T; while(T--){ int n;cin>>n; ll ans=0; for(int i=1;i<=n;i++)cin>>vec[i].x; for(int i=1;i<=n;i++)cin>>vec[i].y; sort(vec+1,vec+1+n,cmp); for(int aj=1;aj*aj<=2*n;aj++){ for(int i=1;i<=n;i++)mp[i]=0; for(int i=1;i<=n;i++){ int ai=vec[i].x,bi=vec[i].y; int bj=ai*aj-bi; //bj合法就对答案产生贡献 if(bj>=1&&bj<=n)ans+=mp[bj]; //如果当前的第i个元素的a等于所枚举的aj,那么此时aj可以绑定一个bi //相当于aj绑定bi这个值是合法的 if(ai==aj)mp[bi]++; } } cout<<ans<<endl; } return 0; }
标签:Count,Pairs,int,aj,BOSS,vec From: https://www.cnblogs.com/zhujio/p/17441088.html