UVA13131 题解

_dijkstra_ · 2022-10-21 12:26:18 · 题解

实际上是一一道红题。

思路

类似质因数检验的方法，容易发现，若 i \mid n，则 \dfrac{n}{i} \mid n。

那么只需枚举前 \sqrt{n} 个数，如果这个数能整除 n，对称地把 \dfrac{n}{i} 也计算上即可。

具体看代码。

代码

码风非主流，凑合着看看。

#include <iostream>
int main()
{
    std::ios::sync_with_stdio(0);
    int _;
    std::cin >> _;
    while (_--){
        int n,k,sum=0;
        std::cin>>n>>k;
        for (int i=1 ; i*i<=n ; i++){
            if (n%i==0){
                if (!(i%k)) sum=sum+i;
                if (i*i!=n && (n/i)%k) sum=sum+n/i; 
            }
        }
        std::cout<<sum<<'\n';
    }
    return 0;
}