yukicoder no.2051 解説

yukicoder no.2051 Divideの解説です．

1. 問題

正整数 $A$, $B$ が与えられます． $A$ の約数かつ $B$ の倍数である正整数の個数を解答してください．

制約

$1 \leq A,B \leq 10^9$

2. 解法

$10^9$ 以下の正整数は，高々約数を $1344$ 個しか持ちません．したがって， $A$ の約数をすべて列挙したうえでそれぞれが $B$ で割り切れるかを判定すればよいです．約数列挙は $O(\sqrt{A})$　で行え，これは十分高速です．

ACコード

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int A,B;
    cin>>A>>B;
    int count = 0;
    for(int i=1;i*i<=A;i++){
        if(A%i != 0) continue;
        int x = i;
        int y = A/i;
        count += (x%B == 0)+(y%B == 0 && x != y);
    }
    cout<<count<<endl;
}

ちなみに，「 $N$ が $N$ 未満のどの正整数よりも多くの約数を持つ」といった性質を持つ正整数 $N$ は無限に存在し，このような数を高度合成数といいます．
$10^9$ 以下の最大の高度合成数は $735134400$ であり，これが $1344$ 個の約数を持ちます．