题解 UVA13131 【Divisors】

直接模拟即可

只是需要知道求$N$的正约数集合的筛法——试除法

从 $1$ 到 $\sqrt{N}$ 的数 $i$ 如果能被$N$整除，那么$\frac{N}{i}$ 也一定能被 $i$ 整除，故复杂度为 O$(\sqrt{N})$.再将中间 $K$ 的倍数筛掉即可.

总复杂度为O$(T\sqrt{N})$,可以通过本题.

/*
 * @Author: junyu33 
 * @Date: 2020-02-05 22:19:40 
 * @Last Modified by:   junyu33 
 * @Last Modified time: 2020-02-05 22:19:40 
 */
#include <bits/stdc++.h>
using namespace std;
int fracsum(int a,int b){
   int ans=0,t=sqrt(a);
   for(int i=1;i*i<=a;i++)
      if(a%i==0){
         if(i%b) ans+=i;
         if((a/i)%b) ans+=a/i;
      }
   if(t*t==a&&t%b) ans-=t; //注意不要减多了，容斥原理要学好
   return ans;
}
int main(){
   int n;cin>>n;
   for(int i=1,a,b;i<=n;i++){
      cin>>a>>b;
      if(b==1){cout<<0<<endl;continue;}
      cout<<fracsum(a,b)<<endl;
   }
   return 0;
}