[過去ﾛｸﾞ] プログラミングのお題スレ Part20 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
562(3): 2022/05/17(火)17:53 ID:UVEhLnaE(1) AAS
さらに、閑古鳥をよびよせるか
[お題] 多倍長では無理!?
整数 S, T が与えられる。(1 <= S <= T <= 400万)
S以上T以下の(連続する)整数の最小公倍数(LCM)をもとめる
答えは, 1000000007(10億7)の余りで出力
1) 6 8 --> 168
6,7,8 の最小公倍数、LCM(6, 7)= 42 --> LCM(42, 8)= 168
2) 10 30 --> 89546497
剰余前は、2329089562800
3) 2567890 3456789 --> ?
省1
563: 2022/05/19(木)21:03 ID:f4mJcXLG(1) AAS
>>562
Haskell
外部ﾘﾝｸ:ideone.com
565: 2022/05/19(木)22:51 ID:vGEyxbeO(1) AAS
>>562 C
外部ﾘﾝｸ:ideone.com
566: 2022/05/20(金)19:19 ID:nM/DB7wD(1) AAS
>>562
外部ﾘﾝｸ:ideone.com
想定解としては、(他の人同様)
求める最小公倍数を素因数分解した形に作るイメージ
400万以下の"素数及び素数べき乗"は、高々28.3万件。
S以上T以下で、素数べき乗が割り切れるかどうかチェックしている。
(方法は T/素数べき乗 > (S-1)/素数べき乗 ならあると, O(1)判定)
ボトルネックは素数を求める部分なので、手抜きしている。
余談)
・4)を多倍長で計算すると173万桁だった(一分程度ででた)
省1
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.031s