Submission #19897

#	Time	Username	Problem	Language	Result	Execution time	Memory
19897		xdoju	팔찌 (kriii4_V)	C++14	100 / 100	579 ms	21512 KiB

V

#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;
}

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

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

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

inline 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;
	}
	if (cnt <= 0) {
		return 0;
	}

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

int mpow[N + 1];
long long psum[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);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			int p = i;
			int q = j / i;
			psum[j] += modprod(mpow[q], phi[p]);
		}
	}

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

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

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

	int ans = moddiv(ssum % MOD, 2);

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

	ans = (ans + 1) % MOD;
	ans = (ans + x) % MOD;
	ans = (ans + y) % MOD;

	printf("%d", ans);
}

int main() {
	//freopen("input.txt", "r", stdin);
	proc();
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94