結果

問題 No.1158 GCD Products easy
ユーザー ID 21712
提出日時 2026-06-06 15:14:12
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 2,257 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,864 ms
コンパイル使用メモリ 278,540 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2026-06-06 15:14:34
合計ジャッジ時間 15,744 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/big"

const M = 1e9+7

func gcd(a, b int) int {
	return int(new(Int).GCD(nil,nil,NewInt(int64(a)),NewInt(int64(b))).Int64())
}

func main() {
	var a,b,n int
	Scan(&a,&b,&n)
	
	ans := 1
	
	var dfs func(i, g int)

	dfs = func(j, g int) {
		if j == n {
			ans = (ans*g)%M
			return
		}
		for i:=a; i<=b; i++ {
			if j == 0 {
				dfs(j+1, i) 
			} else {
				dfs(j+1, gcd(i,g))
			}
		}
	}
	
	dfs(0, 0)
	
	Println(ans)
}

/*
考察

ひとまず制約の違うhardのほうで考察
(easyは問題文のとおりに愚直に計算するだけっぽく見えるし…)

最大10^7
でかいが
おそらく階乗とかはコンビネーションとかは計算可能なサイズぽい？
繰り返し二乗法は言うまでもない
素因数分解も間に合う…？


gcdを決め打ちしたとき引数の数値はどのようになるかを考える
gcd=2なら、2の倍数が並ぶが、それ以外の因数では共通はダメ
例えば
gcd(2,2,2,2,2,2) = 2
gcd(2,6,12,8,20,36) = 2
だが
gcd(12,8,20,36,8,12) = 4
gcd(6,12,36,12,12,6) = 6
gcd(12,12,12,12,12,12) = 12
は gcd=2にはならない
うーん
gcd(i1,i2, ... ,iN) 
gcdの大きいほうから降順で
gcd=Xとなる場合
Xを約数に持つX以上B以下の数の種類数(K=floor(B/X))から組み合わせの数(K^N)を求めて
包除原理に基づいて、Xを約数に持つXより大きい数Yjのsum(gcd=Yj)の総数を引けば、gcd=Xの組み合わせ数となる？

たとえば N=5, B=60 なら
gcd=B=60 となるのは 各i が全部 60 のときだけ
各i が60と各1通りなのでgcd=60は 1^N = 1^5 = 1 通り
この60の約数のうち60以外 2,3,4,5,6,10,12,15,20,30 の組み合わせ数計算のときにgcd=60の組み合わせ数を引いて包徐原理…
素因数列挙ならともかく約数列挙は厳しそう？
エラトステネスの篩と違って素数のときだけ約数を総なめするわけではないし
素因数 2*2*3*5 の各種素数を1回ずつ除いた数 12,20,30 だけ包徐原理するじゃダメ？

このアイデアを実装してみたけど
サンプルと答えが合わないのと
最大の入力のときにTLEするので
たぶんダメ

easyだけ素直に通す

*/
0