SRM 660 div2 hard:Powerit - mayoko’s diary

すぎむ先生からオススメされた問題があるのでそれを解こうと思ってるのですが, 難しくて考え中なのでお茶濁しにこの問題を解きました。

問題

解法

i^(2^k-1) というのは,
i^1 * i^2 * i^4 * ... * i^(2^(k-1))
で表せます。ということで, すべての i に対して上記の値を計算すれば O(nk) で問題を解けます。ただ, 今回の制約では計算量が少し多いのでもう少しだけ工夫をします。

ある整数 x が素因数分解 p1^m1 * p2^m2 * ... と表されるとします。素数についてのみ上記の値 f(p) を計算していたとすると, この整数 x に関する上記の値 f(x) は, f(p1)^m1 * f(p2)^m2 * ... となります。

よって, 素数についてのみ f の値を計算しておくと, 各 i については, O(log i) 程度の計算量で f(i) が求められます。これでも若干計算量は怪しいですが, なんとか時間内に間に合います。

const int MAXN = 1000010;
int prime[MAXN];
ll p[MAXN];

class Powerit {
public:
    int calc(int n, int k, int m) {
        for (int i = 2; i < MAXN; i++) {
            if (prime[i] == 0) {
                for (int j = 2; j * i < MAXN; j++) prime[i*j] = i;
            }
        }
        for (int i = 2; i <= n; i++) {
            if (prime[i] == 0) {
                vector<ll> pp(k);
                pp[0] = i%m;
                for (int j = 0; j < k-1; j++) {
                    pp[j+1] = (pp[j]*pp[j]) % m;
                }
                p[i] = 1;
                for (int j = 0; j < k; j++) (p[i] *= pp[j]) %= m;
            }
        }
        ll ret = 1;
        for (int i = 2; i <= n; i++) {
            int tmp = i;
            ll plus = 1;
            while (prime[tmp] != 0) {
                (plus *= p[prime[tmp]]) %= m;
                tmp /= prime[tmp];
            }
            (plus *= p[tmp]) %= m;
            ret += plus;
        }
        return (int)(ret%m);
    }
};