3164. 优质数对的总数 II
思路：先找出可以被k整除的nums[i].
方法一：统计因子。
1、找出数组nums1每个元素的因子，用哈希表来记录每个因子出现的次数。然后再遍历数组nums2进行累加即可。
class Solution {
public:
const int N=1e6+10;
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
//记录数组nums1每个元素的所有因子出现的次数
vector<int> sta(N,0);
for(int i=0;i<nums1.size();i++){
if(nums1[i]%k) continue;
int tmp=nums1[i]/k;
for(int j=1;j<=tmp/j;j++){
if(tmp%j==0){
sta[j]++;
if(tmp/j!=j) sta[tmp/j]++;
}
}
}
//遍历数组nums2进行累加
long long ans=0;
for(int i=0;i<nums2.size();i++){
ans+=sta[nums2[i]];
}
return ans;
}
};
方法二：倍增枚举。
1、先用数组sta记录可以被k整除的nums[i]。
2、再用哈希表map来统计nums2的元素。这里是避免大量重复的元素造成的时间浪费。
3、遍历哈希表map里的元素，来进行倍增。累计数组sta出现的次数即可
class Solution {
public:
const int N=1e6+10;
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
//记录可以被k整除的nums[i]
vector<int> sta(N,0);
//记录最大的nums1[i]/k，倍增时不超过这个数即可
int mx=0;
for(int i=0;i<nums1.size();i++){
if(nums1[i]%k) continue;
sta[nums1[i]/k]++;
mx=max(mx,nums1[i]/k);
}
//统计nums2的元素，避免大量重复的元素造成的时间浪费。
unordered_map<int,int> mp;
for(auto t:nums2){
mp[t]++;
}
long long ans=0;
//遍历哈希表map里的元素，进行倍增。
for(auto t:mp){
for(int j=1;j*t.first<=mx;j++){
//累计数组sta出现的次数即可
ans+=(long long)sta[j*t.first]*t.second;
}
}
return ans;
}
};