Submission #474637

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474637	2021-09-19T08:17:09 Z	egod1537	팔찌 (kriii4_V)	C++14	100 / 100	596 ms	31608 KB

V

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

typedef pair<ll, ll> pi;
#define var first
#define cnt second

ll pwk[1000001], phi[1000001], low[1000001], inv[1000001];

ll pow(ll x, ll p) {
	ll ret = 1, piv = x % mod;
	while (p) {
		if (p & 1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret;
}
ll revmod(ll x) { return pow(x, mod - 2) % mod; }	
ll r2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	ll n, k; cin >> n >> k;

	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			if (!low[j]) low[j] = i;
		}
		phi[i] = i;
		for (int j = i; j != 1; ) {
			int p = low[j];
			while (j % p == 0) {
				j /= p;
			}
			phi[i] = (1ll * phi[i] * (p - 1)) / p;
		}
	}

	pwk[0] = 1;
	for (int i = 1; i <= 1000000; i++) {
		pwk[i] = (pwk[i - 1] * k) % mod;
		inv[i] = revmod(i);
	}
	r2 = revmod(2);

	ll ans = 2;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			ll diff = (((pwk[i] * phi[j / i]) % mod) * inv[j])%mod;
			ans = (ans + diff) % mod;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i % 2 == 0) ans = (ans + (1 * (k + 1) * pwk[i / 2] % mod) * ((mod + 1) / 2) % mod)%mod;
		else ans = (ans + pwk[i / 2 + 1])%mod;
	}
	ans *= (mod + 1) / 2;
	ans %= mod;
	cout << ans;

	return 0;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	15940 KB	Output is correct
2	Correct	171 ms	15992 KB	Output is correct
3	Correct	166 ms	15896 KB	Output is correct
4	Correct	162 ms	15888 KB	Output is correct
5	Correct	164 ms	15920 KB	Output is correct
6	Correct	162 ms	15932 KB	Output is correct
7	Correct	163 ms	15928 KB	Output is correct
8	Correct	175 ms	15896 KB	Output is correct
9	Correct	164 ms	15940 KB	Output is correct
10	Correct	162 ms	15908 KB	Output is correct
11	Correct	165 ms	15852 KB	Output is correct
12	Correct	178 ms	15940 KB	Output is correct
13	Correct	166 ms	15844 KB	Output is correct
14	Correct	162 ms	16068 KB	Output is correct
15	Correct	163 ms	15852 KB	Output is correct
16	Correct	161 ms	15940 KB	Output is correct
17	Correct	161 ms	15900 KB	Output is correct
18	Correct	164 ms	15840 KB	Output is correct
19	Correct	162 ms	15984 KB	Output is correct
20	Correct	162 ms	15892 KB	Output is correct

Subtask #2

94.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	15872 KB	Output is correct
2	Correct	165 ms	15940 KB	Output is correct
3	Correct	166 ms	15968 KB	Output is correct
4	Correct	187 ms	16708 KB	Output is correct
5	Correct	341 ms	25588 KB	Output is correct
6	Correct	443 ms	27720 KB	Output is correct
7	Correct	327 ms	25024 KB	Output is correct
8	Correct	422 ms	27220 KB	Output is correct
9	Correct	473 ms	28832 KB	Output is correct
10	Correct	555 ms	30832 KB	Output is correct
11	Correct	482 ms	29004 KB	Output is correct
12	Correct	526 ms	30424 KB	Output is correct
13	Correct	325 ms	24576 KB	Output is correct
14	Correct	554 ms	29852 KB	Output is correct
15	Correct	318 ms	24208 KB	Output is correct
16	Correct	345 ms	25652 KB	Output is correct
17	Correct	591 ms	31476 KB	Output is correct
18	Correct	362 ms	25288 KB	Output is correct
19	Correct	420 ms	27320 KB	Output is correct
20	Correct	596 ms	31608 KB	Output is correct