CodeChef Chef and cities - mayoko’s diary

問題

数列 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;
}