Submission #474771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474771	2021-09-19T16:03:36 Z	egod1537	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	31816 KB

V

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

#include<bits/stdc++.h>
#include <unordered_map>

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[2000001], phi[1000001], low[1000001];
bitset<1000001> vit;
vector<ll> prime;

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;
ll func(ll n, ll k) {
	ll ans = 0;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ans = (ans + phi[n / i] * pwk[i])%mod;
			if (n / i != i) ans = (ans + phi[n / (n / i)] * pwk[n / i])%mod;
		}
	}
	if (n % 2) ans = (ans + (n * pwk[n / 2 + 1]) % mod) % mod;
	else {
		ll pw = (pwk[n / 2] + pwk[n / 2 + 1]) % mod;
		ans = (ans + (((n * pw) % mod) * r2) % mod) % mod;
	}

	return (ans * revmod(2 * n)) % mod;
}

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

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

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

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

	ll ans = 1;
	for (int i = 1; i <= n; i++) ans = (ans + func(i, k)) % mod;
	cout << ans;

	return 0;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	31732 KB	Output is correct
2	Correct	148 ms	31628 KB	Output is correct
3	Correct	146 ms	31680 KB	Output is correct
4	Correct	143 ms	31616 KB	Output is correct
5	Correct	145 ms	31816 KB	Output is correct
6	Correct	149 ms	31696 KB	Output is correct
7	Correct	147 ms	31668 KB	Output is correct
8	Correct	146 ms	31684 KB	Output is correct
9	Correct	148 ms	31708 KB	Output is correct
10	Correct	149 ms	31652 KB	Output is correct
11	Correct	150 ms	31628 KB	Output is correct
12	Correct	145 ms	31684 KB	Output is correct
13	Correct	145 ms	31720 KB	Output is correct
14	Correct	147 ms	31692 KB	Output is correct
15	Correct	147 ms	31680 KB	Output is correct
16	Correct	146 ms	31648 KB	Output is correct
17	Correct	151 ms	31724 KB	Output is correct
18	Correct	147 ms	31636 KB	Output is correct
19	Correct	148 ms	31632 KB	Output is correct
20	Correct	143 ms	31644 KB	Output is correct

Subtask #2

0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	31672 KB	Output is correct
2	Correct	146 ms	31692 KB	Output is correct
3	Correct	146 ms	31684 KB	Output is correct
4	Correct	226 ms	31728 KB	Output is correct
5	Execution timed out	1081 ms	31704 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-