はじめに
正の整数 を固定します. として, を考えることはよくあります. ここで はを超えない最大の整数です.
を自由に動かすとき, のとりうる値の種類の数は です.(A055086 - OEIS)
これらの値をすべて列挙する方法で, かなり楽なものを見つけたので今回はこれを紹介します.
コード
//CPP #include <bits/stdc++.h> using namespace std; int main(){ long long N; cin >> N; long long i = N; while (i > 0){ long long v = N / i; long long j = N / (v+1); cout << v << endl; i = j; } }
#PYTHON N = int(input()) i = N while i > 0: v = N // i j = N // (v+1) print(v) i = j
のとりうる値を小さい順に表示させています.
このとき, は となるような最大の値になって, は でなくなる最大の値です.
つまり, ]という半開区間が となるようなの区間となります.
証明?
(すなわち)のときはokです. の次にとりうる値は, 以上です.
このとき, すなわち が成り立ちます.
これを満たすの最大値はです.
よって, 帰納的に最大という条件が満たされます. のときは, となるのでプログラムが終了します.
例題
正の整数に対して, を求める問題です.
この問題は平方分割で解くことができますが, 今のやり方で解いてみます.
は, となるの個数であることに注目します.
これは答えに だけ寄与します.
#include <bits/stdc++.h> using namespace std; int main(){ long long N, i, j, v, ans; cin >> N; i = N; ans = 0; while (i > 0){ v = N / i; j = N / (v+1); ans += v * (i-j); i = j; } cout << ans << endl; }
練習問題
Codeforces Round #809 (Div.2) D2. Chopping Carrots (Hard Version)
https://codeforces.com/contest/1706/problem/D2
このコードは, この問題の考察中に生まれたものです. メモリ制限が厳しくPythonではあまりオススメできません
関連するもの
次のmaspyさんの記事で, がよく出てきます.
Dirichlet 積と、数論関数の累積和 - maspyのHP
https://maspypy.com/dirichlet-%E7%A9%8D%E3%81%A8%E3%80%81%E6%95%B0%E8%AB%96%E9%96%A2%E6%95%B0%E3%81%AE%E7%B4%AF%E7%A9%8D%E5%92%8C