Codeforces 226C (140C) Anniversary

問題

n番目のフィボナッチ数をFiとする。
与えられた数l, r, kに対して、
Fl, Fl+1, ..., Frから異なるk個の数を選び、その最大公約数を求める。
全ての選び方のうち、最大公約数が最大になるようなときの、最大公約数をmod mで求めよ。

制約条件

l, r≦10^12
2≦k≦r - l + 1

方針

GCD(Fi, Fj) = F[GCD(i, j)]という関係を使えば、
l, l+1, ..., rからk個の数を選んで、GCMを最大化するという問題を解けばよいことがわかる。

GCMをqとしたとき、
l, rの間に含まれるqの倍数の個数は、r/q + (l-1)/q（割り算は切り捨て）
これがk以上ならよくて、k以上のうち最大になるqを見つけたい。

r/q + (l-1)/qの値が変化するqのところだけ見ればよい。
a/qがどこで値が変化するかというと、
√aまでは1ごとに値が変化して、それより大きいときは、
a/p = qとなるpごとに値が変化する。

なので、この値の変わり目は2 * √a個くらいしかない
これをl-1についても調べて、その変わり目上だけを実際に確かめればよい。

あとはn番目のフィボナッチ数を求めるだけだが、これは行列の累乗でlogの時間で求められる。

ソースコード

ll mod, l, r, k;

typedef vector<vi> M;
inline M operator*(const M & a, const M &b){
	M c(a.size(), vi(b[0].size()));
	rep(i, c.size()) rep(j, c[0].size()){
		ll s = 0;
		rep(k, a[0].size()) s += (ll)a[i][k] * b[k][j] % mod;
		c[i][j] = s % mod;
	}
	return c;
}
inline M pow(M a, ll m){
	M res(a.size(), vi(a.size()));
	rep(i, a.size()) res[i][i] = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * a;
		a = a * a;
	}
	return res;
}
ll fib(ll n){
	M mat(2, vi(2, 1));
	mat[1][1] = 0;
	mat = pow(mat, n);
	return mat[1][0];
}
int main(){
	cin >> mod >> l >> r >> k;
	
	ll a = 1;
	vi cand;
	for(ll i = 1; i * i <= r; i++){
		cand.pb(i);
		cand.pb(r / i);
	}
	for(ll i = 1; i * i <= l - 1; i++){
		cand.pb((l - 1) / i);
	}
	rep(i, cand.size()) if(r / cand[i] - (l - 1) / cand[i] >= k)
		a = max(a, cand[i]);
	
	cout << fib(a) << endl;
	return 0;
}