結果
問題 | No.2480 Sequence Sum |
ユーザー |
|
提出日時 | 2023-09-22 22:05:46 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 3 ms / 500 ms |
コード長 | 2,333 bytes |
コンパイル時間 | 5,620 ms |
コンパイル使用メモリ | 207,744 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-26 14:39:29 |
合計ジャッジ時間 | 5,965 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 |
ソースコード
import std;void main () {int N = readln.chomp.to!int;solve(N);}void solve (int N) {// 正整数a, b自然数k, lを用いて、N = ak + bl// 制約から、1 <= a, b = a+1なので、// N = ak + (a+1)l// = a(k+l) + l// N-l = a(k+l)// k+l = (N-l)/a// あまり筋が良くなさそう。剰余の観点から考える。// aと項数xを決めたとき、実現できる範囲は[a*x+1, (a+1)*x-1]になる。// 2<=xに対して一つでもNが上記の範囲に入るような1<=aを見つけられれば良い。// aとa+1を考える。// この時、範囲は[a*x+1, (a+1)*x-1]と[(a+1)*x+1, (a+2)*x-1]を表すことができる。// 実現できない数というのは、この間に挟まっているようなもの、または下限よりも下にあるもの。// つまり、// 1. 2<=xに対して、a*xと表される数// 2. 2<=xに対して、x以下の数// 自明なxの上界はN-1になる。// 約数列挙で解けるやんけ!if (N == 1 || N == 2) {writeln(0);return;}int ans = N - cast(int) enumDiv(N).length;writeln(ans);}struct enumDiv {import std.algorithm;import std.exception;import std.format;int begin = 0, end;long[] div;this (long N) {auto msg = format("Line : %s, N must be greater than or equal to 0. Your input = %s.", __LINE__, N);enforce(0 <= N, msg);foreach (x; 1..N+1) {if (N < x * x) {break;}if (N % x == 0) {div ~= x;if (x * x != N) {div ~= N / x;}}}div.sort;end = cast(int)div.length;}size_t length () {return div.length;}long opIndex (size_t i) {return div[i];}long[] opSlice (size_t i, size_t j) {return div[i..j];}size_t opDollar () {return div.length;}bool empty () const {return begin == end;}void popFront() {begin++;}long front () const {return div[begin];}void popBack () {end--;}long back () const {return div[end - 1];}}