Submission #19882

# Submission time Handle Problem Language Result Execution time Memory
19882 2016-02-25T06:37:03 Z xdoju 팔찌 (kriii4_V) C++14
6 / 100
16 ms 13724 KB
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

const int MOD = 1000000007ll;

int modpow(int r, int n) {
	int ret = 1;
	while (n > 0) {
		if (n % 2 > 0) {
			ret = ((long long)ret * r) % MOD;
		}
		r = ((long long)r * r) % MOD;
		n /= 2;
	}
	return ret;
}

int modinv(int n) {
	return modpow(n, MOD - 2);
}

int modprod(int a, int b) {
	a = a % MOD;
	b = b % MOD;
	return ((long long)a * b) % MOD;
}

int modprod(int a, int b, int c) {
	c = c % MOD;
	return (modprod(a, b) * (long long)c) % MOD;
}

int moddiv(int a, int b) {
	return ((long long)a * modinv(b)) % MOD;
}

const int N = 1000000;
int lp[N + 1];
int phi[N + 1];
vector<int> pr;

void sieve() {
	phi[1] = 1;
	for (int i = 2; i <= N; ++i) {
		if (lp[i] == 0) {
			lp[i] = i;
			phi[i] = i - 1;
			pr.push_back(i);
		}
		else {
			if (lp[i] == lp[i / lp[i]]) {
				phi[i] = phi[i / lp[i]] * lp[i];
			}
			else {
				phi[i] = phi[i / lp[i]] * (lp[i] - 1);
			}
		}
		for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j) {
			lp[i * pr[j]] = pr[j];
		}
	}
}

int geoseries(int k, int cnt) {
	if (k == 1) {
		return cnt;
	}

	int ret = (modpow(k, cnt) - 1 + MOD) % MOD;
	ret = modprod(ret, k);
	return moddiv(ret, k - 1);
}

int mpow[N + 1];

void proc() {
	sieve();

	int n, k;
	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; ++i) {
		mpow[i] = modpow(k, i);
	}

	int ssum = 0;
	for (int i = 1; i <= n; ++i) {
		int t = 0;

		int lmt = (int)(sqrt(i) + 0.00001);
		for (int p = 1; p <= lmt; ++p) {
			if (i % p != 0) {
				continue;
			}
			int q = i / p;

			t = (t + modprod(mpow[q], phi[p])) % MOD;
			if (p != q) {
				t = (t + modprod(mpow[p], phi[q])) % MOD;
			}
		}
		t = moddiv(t, i);
		ssum = (ssum + t) % MOD;
	}

	int ans = moddiv(ssum, 2);

	int x = moddiv(modprod(k + 1, geoseries(k, n / 2)), 4);
	int y = moddiv(geoseries(k, (n + 1) / 2), 2);

	printf("%d", (ans + 1 + x + y) % MOD);
}

int main() {
	//freopen("input.txt", "r", stdin);
	proc();
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 15 ms 13724 KB Output is correct
2 Correct 15 ms 13724 KB Output is correct
3 Correct 15 ms 13724 KB Output is correct
4 Correct 15 ms 13724 KB Output is correct
5 Correct 15 ms 13724 KB Output is correct
6 Correct 15 ms 13724 KB Output is correct
7 Correct 15 ms 13724 KB Output is correct
8 Correct 11 ms 13724 KB Output is correct
9 Correct 11 ms 13724 KB Output is correct
10 Correct 8 ms 13724 KB Output is correct
11 Correct 11 ms 13724 KB Output is correct
12 Correct 16 ms 13724 KB Output is correct
13 Correct 15 ms 13724 KB Output is correct
14 Correct 12 ms 13724 KB Output is correct
15 Correct 15 ms 13724 KB Output is correct
16 Correct 11 ms 13724 KB Output is correct
17 Correct 15 ms 13724 KB Output is correct
18 Correct 15 ms 13724 KB Output is correct
19 Correct 15 ms 13724 KB Output is correct
20 Correct 15 ms 13724 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 11 ms 13724 KB Output is correct
2 Correct 15 ms 13724 KB Output is correct
3 Incorrect 12 ms 13724 KB Output isn't correct
4 Halted 0 ms 0 KB -