Odd Even Divisor

2 secs 1024 MB

parentheses

問題

提出

テストケース

解説

この問題はループを用いて愚直に約数の個数を数えることで $O(N^2)$ で解くことができます。

問題文でも言及されている通り、整数 $x$ $(1 ≦ x ≦ N)$ の正の約数 $d$ は $1 ≦ d ≦ x$ の範囲にのみ存在するため、この範囲を探索すれば十分です。実装の際は $x$ の偶奇による場合分けに注意してください。

なお、この問題は「正の約数の個数のテーブルを作る問題」に帰着されるため $O(N \mathrm{log} N)$ で解くこともできます（もっと高速に解く方法も存在します）。下記の問題も参考にしてください。

Number of Divisors 2

解答例

解答例（C++）

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
​
int main() {
    int N, A, B; cin >> N >> A >> B;
​
    int ans = 0;
    for (int x = 1; x <= N; x++) {
        int num = 0;  // 約数の個数
        for (int d = 1; d <= x; d++) {
            if (x % d == 0) { num++; }
        }
        if (x % 2 == 1 && num == A) { ans++; }
        if (x % 2 == 0 && num == B) { ans++; }
    }
​
    cout << ans << endl;
​
    return 0;
}

解答例（Python）

xxxxxxxxxx
 
import sys
​
input = sys.stdin.readline
​
​
def main():
    N, A, B = map(int, input().split())
​
    ans = 0
    for x in range(1, N + 1):
        num = 0  # 約数の個数
        for d in range(1, x + 1):
            if x % d == 0:
                num += 1
        if (x % 2 == 1) and (num == A):
            ans += 1
        if (x % 2 == 0) and (num == B):
            ans += 1
​
    print(ans)
​
​
if __name__ == "__main__":
    main()