nc = [n/c-1,0].max*c. N を LCM(A,B) と半端に分けて考える代わりに、LCM(A,B)１回分と半端をその他として取り分けて考える。正直よくわかりません。一晩経ってひらめいて試したら AC だっただけ。■■■@kyopro_friends「1 以上 N 以下の整数のうち、2 以上 M 以下の数を約数に持たないものの個数を求めて下さい。[制約] ＊1≦N≦10^{16} ＊1≦M≦20 ＊入力はすべて整数」 DP と包除原理でサンプルの２までは答えが合った>解答。M≦72 のサンプル３は TLE になる。むむむ。関連するマシュマロ質問に「素数の積」とあったので素数だけを取り出してみたらサンプルの３も合ったっぽい(先頭と末尾の数桁の一致を確認)>解答２。まだまだだなあ。■@2023-01-26 今日のお風呂での話。20230124 に中国剰余定理で解いた ABC286-F「Guess The Number 2」の反芻をしているときに、kyopro_friends さんの即興問題とのあいだの共通点に考えが広がって、もてあそんでいるときに「この問題なら、最初から割り算で計算すればオーバーフローのことを気にする必要はないけどねー」の意味がひらめいた。自分の解答２でいうと最後から２行目に N/c という式があって、c というのが素数の積。C++ のように整数型のビット長が固定の言語では c がオーバーフローするおそれが現実的な範囲にある。ここで、割る数(c)を大きくする代わりに割られる数(N)を小さくしていくのも同様にありだなーと、あのツイートはこういう意味だったのかと、一日遅れで頭に血が巡ってきたという話。これがファイナルアンサー>解答３。割る数(a)は M 以下だし割られる数(n)は N 以下。入力を超える数がないからオーバーフローもない。