CodeChef Chef and cities
問題
数列 F が与えられる。以下のクエリを処理せよ。
- F[p] = f とする
- R が与えられるので, F[0]*F[R]*F[2*R]*...*F[(N-1)/R*R] の値について, 10 進法における一番上の数, 10^9+7 で割ったあまり を求める
解法
自分の解法だと 100 点取ろうとしたときに 5 点分が確保できなかったので 5 点分の時は別に処理しています。
10 進法の一番上の数を求めるときは, log を取るのがよくやることです(大学受験でよく出るアレ)。
クエリの処理の仕方ですが, 取り合えず最初に mult[i] = (R = i としたときの 10^9+7 で割ったあまり), logs[i] = (R = i としたときの log[F[i*d]] みたいなやつの和) を求めておきます。これは N*(1+1/2+...+1/N) なので O(N log N) でできます。
また, F[p] = f と変更したとき, mult, logs が変化するのは, p の約数の部分だけです。10^5 以下で約数が最大のものは 128 個なので, 十分高速に mult, logs の必要な部分を更新できます。
ll mod_pow(ll x, ll p, ll MOD) { ll a = 1; while (p) { if (p%2) a = a*x%MOD; x = x*x%MOD; p/=2; } return a; } // mod_inverse ll mod_inverse(ll a, ll m) { return mod_pow(a, m-2, m); } const int MOD = 1e9+7; const int MAXN = 100100; int F[MAXN]; Real logs[MAXN]; ll mult[MAXN]; vector<int> divs[MAXN]; Real cand[15]; int main() { for (int i = 1; i <= 10; i++) cand[i] = log10l(i); for (int i = 1; i < MAXN; i++) { for (int j = 1; i*j < MAXN; j++) { divs[i*j].push_back(i); } } int N; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", F+i); if (N <= 10) { int Q; cin >> Q; while (Q--) { int type; scanf("%d", &type); if (type == 1) { int p, f; cin >> p >> f; F[p-1] = f; } else { int R; cin >> R; ll ans = 1; for (int i = 0; i < N; i += R) { ans *= F[i]; } printf("%c %lld\n", to_string(ans)[0], ans%MOD); } } } else { for (int i = 1; i <= N; i++) { mult[i] = 1; for (int j = i; j < N; j+=i) { (mult[i] *= F[j]) %= MOD; logs[i] += log10l(F[j]); } } int Q; scanf("%d", &Q); while (Q--) { int type; scanf("%d", &type); if (type == 1) { int p, f; scanf("%d %d", &p, &f); p--; if (p) { auto div = divs[p]; Real to = log10l(f), from = log10l(F[p]); ll inv = mod_inverse(F[p], MOD); for (int d : div) { (mult[d] *= f) %= MOD; (mult[d] *= inv) %= MOD; logs[d] += to - from; } } F[p] = f; } else { int R; scanf("%d", &R); Real tmp = logs[R] + log10l(F[0]); Real rest = tmp - (int)(tmp); int ans1 = 0; for (int i = 1; i < 10; i++) { if (cand[i] <= rest && rest < cand[i+1]) { ans1 = i; break; } } ll ans2 = (mult[R]*F[0]) % MOD; printf("%d %lld\n", ans1, ans2); } } } return 0; }