白駿解題-少数連続1644回

📜 理解问题

1つ以上の連続する少数の和が表すことができる自然数がある.いくつかの自然数の例を挙げると以下のようになります.
3:3(1種)
41:2+3+5+7+11+13=11+13+17=41(3種類)
53:5+7+11+13+17=53(両方)
しかし、いくつかの自然数は連続的な少数の和で表すことができず、20は一例である.7+13を計算すると20ですが、7と13は連続していないので適切な表現ではありません.また、小数は1回の加算にしか使用できないため、3+5+7のような表現にも適していない.
自然数が与えられた場合、連続する小数の和で自然数を表すことができる場合は、プログラムを作成して解きます.

💡 問題の再定義

自然数Nが連続する小数の和として表すことができれば、数字を出力する.

▼▼▼計画作成

この問題は2つの段階を経なければならない.

いちじしょうすうけってい
まずNまでの数字の中から少数を選ぶ.時間の複雑さを減らすために、エラトステネスのふるいを用いて素数を求める.

二次部分和
部分和を求めるときは、その値がNであるかを確認します.この場合,自然数Nの範囲は400万であるため,ダブルポインタで実現できるO(N),すなわち線形時間で解決可能なアルゴリズムを用いる必要がある.

💻 計画の実行

if __name__ == '__main__':
    N = int(input())
    if N == 1:
        print(0)
    else:
        nums = [1 for i in range(N+1)]
        prime_nums = []
        # 에라토스테네스의 체
        for i in range(2, N+1):
            if nums[i]:
                prime_nums.append(i)
                for j in range(i, N+1, i):
                    nums[j] = 0
        start = 0
        end = 0
        prime_nums_len = len(prime_nums)
        prime_sum = 0
        result = 0

        while True:
            if prime_sum >= N:
                if prime_sum == N:
                    result += 1
                prime_sum -= prime_nums[start]
                start += 1
            else:
                if end == prime_nums_len:
                    prime_sum -= prime_nums[start]
                    start += 1
                else:
                    prime_sum += prime_nums[end]
                    end += 1

            if start == end:
                break
        print(result)

🤔 振り返る

問題自体は少数の判定と投票者の組み合わせであり,二つの段階を正しく解決できれば容易に解決できる問題である.