[C++知识库]Codeforces Round #777 (Div. 2) D. Madoka and the Best School in Russia

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int t,x,d,dp[N];
vector<int> v;
unordered_map<int,int> mp;
void run(){
    v.clear();mp.clear();
    for(int i=1;i*i<=x;i++){
        if(x%i==0){
            v.push_back(i);
            if(x/i!=i)v.push_back(x/i); 
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        if(v[i]%d==0&&(v[i]/d)%d!=0){
            mp[v[i]]++;
            for(int j=0;j<v.size();j++){
                if(v[j]%v[i]==0){
                    // cout<<v[i]<<" "<<v[j]<<endl;
                    mp[v[j]]+=mp[v[j]/v[i]];
                }
            }
        }
    }
    // cout<<mp[x]<<endl;
    if(mp[x]>=2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&x,&d);
        run();
    }
}