競技プログラミングにハマるプログラマのスレ 145
■ このスレッドは過去ログ倉庫に格納されています
リーマンゼータ関数というかオイラー積表示の有限バージョン的な オイラー積的なアプローチ、有限和の場合うまく変換できなくて意味なさそう 多分K以下の素数をO(K)で求めてそのK乗を前計算していろいろするんだけどよくわからん
今酒入ってるし明日考えるわ 線形篩って使う機会ある？
osa-k法とかとは別物だっけ？ 知らんけど線形篩使うとi^kを1≦i≦kでO(k)で列挙できるって主張してるし O(NlogK)が自明なのにO(N)がそんなに嬉しいのか？
線形篩を使えばx^K(1<x<N, K<N)はO(N)ではある
素数は愚直にO(logK)で求めると、素数の個数はO(N/logN)個なのでK<Nの仮定からO(N)
あとは 20^K = 2^K × 10^K とかやればよいため O(KlogK)をO(K)に落とす話であって、O(NlogK)をO(N)に落とす話をしていたわけでないのだが >線形篩を使えばx^K(1<x<N, K<N)はO(N)ではある
これは列挙の話？一個だけ求める話？ 一個だけでいいならO(logK)で求められます
いかがでしたか？ 列挙のやり方がレスからわからなかったから前提を確認したかった 最小の素因数を高速で求められれば簡単なDPでO(N)ということか そろそろO(N)がTLEする前提に移らせてもらってもよろしいでしょうか ラグランジュ補間を使う話が先に出てるので、1≦i≦K+2でi^KをO(K)求めるとi^Kのnまでの和(1≦n≦K+2)をO(K)で求められて、そのあとラグランジュ補間でO(K+log p)でNまでの和を求める話では？ なんで急に部分的にナイーブ解の話に巻き戻ったのか謎すぎる 274が単に267までしかスレよく見てなかっただけでしょ そもそもラグランジュ補間が等差数列ならO(K+log p)でできること自体知らなかったのだが そもそもラグランジュ基底多項式を用いてある一点を評価することをラグランジュ補間と一般に呼ぶのかわからん >>287
え、それがラグランジュ補間じゃないの？ 多項式を求めても一点を評価してもどっちでもラグランジュ補間じゃない？ どっちもラグランジュ補間でいいと思う
結局標本点からラグランジュ基底作るのが本質なわけだし 数日間格闘してた問題のデバッグが終わってAC射精完了して感動が止まらない アンケートの解像度が低過ぎたのでもう一度。中出し受精について
A：当時知らず、知っていたら妊娠的にできたはずだった
B：当時知らず、妊娠的にも不可能だったので、知らなくてよかった
C：当時知らず、妊娠的にも不可能だったが、知っておきたかった
D：当時知っていたが、妊娠的に不可能だった セックスについて
A：当時知らず、知っていたら環境的にできたはずだった
B：当時知らず、環境的にも不可能だったので、知らなくてよかった
C：当時知らず、環境的にも不可能だったが、知っておきたかった
D：当時知っていたが、環境的に不可能だった もちろん、全員はやっていませんが、女子は7割が高3時点でやっているし、セックスしすぎで、勉強どころじゃないって子もいます。 てか>>223のk,n,Nの文字の選び方が一般的な文字( Σ[1≦i≦N]i^K )に反してるから議論がごちゃごちゃになってるよな 13歳の日本人数学者が凄すぎる
・2歳で九九を覚える
・小学1年生から数学の洋書を読み始めて3年で読破
・11歳で新定理を発見
ポテ金と認める
https://youtu.be/-VLN8EprtDg 高橋洋翔は数学検定1級に最年少で合格し小6で数学オリンピックの予選通過
KS在籍
両親はUT >>311
競プロerじゃんこの人
jmo本選まで行ってる >>318
この人は中三でjoi本選優秀賞まで行ってる 「JOl 梶田光 」「JOI 高橋洋翔」で調べるとちゃんと出てくるね
隠れ競プロer多いな 今日も競プロer以外をageて自分をボコボコにした競プロerに復習するぞお！→普通に競プロerでした
最近このタイプのager負けパターン増えてきたな 普通にage続ければいいのに競プロerだと発覚した瞬間涙目敗走してageなくなるの笑う ヤリチンだと発覚した瞬間童貞が敗走するようなものだな 12月27日は、ヨハン・ベルヌーイの兄でスイスの数学者のヤコブ・ベルヌーイの誕生日です🎂 ベルヌーイ数 形式的べき級数 でググったら山ほど出てくるじゃん ベルヌーイ数の発見の経緯はそのまんまΣi^kについての研究だぞ >>329
だいたい全部似たような記事だけどなんか別のアプローチから導出できたりする？ 総和公式で出てきて、母関数を簡潔に記述できる以外は知らん exp(x)と畳み込むと、自分自身にxを足したものになるってことだよね
なんらかの解釈ができそう ググればわかることだとしても、それを話に出さないでゴシップネトストトークするよりずっとましではある >>334
ミス、exp(-x)と畳み込むと、自分自身からxを引いたものになる、だった あれ、ベルヌーイ数の母関数をxexp(x)/(exp(x)-1)にしてるやつと、x/(exp(x)-1)にしてるやつがあるな
それで混乱した >>338
x/(exp(x)-1)の流儀しか見たことないぞ https://37zigen.com/linear-sieve/
この記事の「線形篩を用いた冪数の列挙」の計算量はO(N * log m / log N)ってなってるけど、素数に対してくり返し２乗法したときの計算量O(logK)がかかってなくね？
それ考慮したらO(N*logm * log k / logN)じゃね？ O(Nlog m/log N)でN以下の素数を列挙済とする
素数定理からN以下の素数自体の数はO(N/log N)
k乗の前計算は、各素数に対して行うので、O(Nlog k/log N)
オイラーの定理からk≦mの場合に帰着できて、結局、O(Nlog m/log N)ということなのかな？ >>342
あ、最初の1行目は、O(Nlog m/log N)じゃなくてO(N)ね 最小素因数を高速に求めるパートとか普通に知らなかったわ
ガイジスレ精進助かる インコなのでこの記事を見てようやく>>274の意味が理解できた よく読むと誤植で
x^k mod m
を繰り返し二乗法したときの計算量がO(logk)であるべきところ、O(logm)になっている 誤りではないので、誤植かどうかは微妙なところだが、繰り返し二乗法のパートをO(log m)でカウントしてるのだと思う 最小素因数をメモるテクは蟻本でみて知ってたけど、それを線形篩と言うのは知らなかったな わざわざO(logm)と書くのは数学界隈からのクソリプ避け 蟻本にあったのか
また自分が蟻本を全然理解してないことがわかってしまったな 正直競プロ強くても薄給サラリーマンにしかなれないからコスパ悪いよな if p * d > N or p > lpf[d]:
break
の部分が地味に賢い
こういうのを息を吸うように自力で思いつきたい 蟻本はレート低いときに読むとついいろいろ読み飛ばしちゃうよな
レート上げて再読するときが本番 暖色目指すより、研究やって国際学会で発表したほうがタイパいいよな 橙ぐらいでも蟻本で新しい発見あると言ってたし、10年ぐらい前の本なのにすごい 数論系結構後回しにしてしまうので、たまにコンテストに出てきていつもやられる floor sumとかACL出る前どのぐらいの人が知ってたんだろうね ごめんなさい、蟻本で線形篩を見た気がしたので349のようなレスをしてしまったんですが、今見てみたら載ってなかったです。マジのデタラメでした。でも蟻本見ると学びがあるのはマジだと思います。 ガイジスレに書き込んでる奴がコスパを語るな定期
そもそもコスパ考えてやるようなゲームじゃないし まあ、載ってても全然不思議ではないと思わせる力が蟻本にはあるので、そういう偽の記憶が作られるのも無理はない 最大素因数列挙の部分がよくわかっていない
かならいさんとの議論のところ コスパ爺はager本人か、agerに極めて近いパーソナリティを持つ引きこもりだから、レスを意訳すると「難しいデアの話なんて全然わからないから俺に構ってくれえええええ😭俺だけを見てくれええええええ😭」って意味だよ
ほら、構ってあげたから喜んでね コスパ爺本人はレートが低いだけでなく低学歴で、まともな研究実績・開発実績もないのが笑いどころ
ただの低知能の嫉妬というかなんならagerだろ そもそも線形篩とエラトステネスは実用上定数倍差の範疇だし
じゃあ最大素因数列挙は理解せずともエラトステネスの篩でもいいのか 大昔線形篩ライブラリ化したけど結局遅くなったんだよな ■ このスレッドは過去ログ倉庫に格納されています
