oj.uz

답안 #474637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474637 2021-09-19T08:17:09 Z egod1537 팔찌 (kriii4_V) C++14
100 / 100
 596 ms 31608 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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