Submission #474770

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474770	2021-09-19T16:02:50 Z	egod1537	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	31828 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 += phi[n / i] * pwk[i];
			if (n / i != i) ans += phi[n / (n / i)] * pwk[n / i];
		}
	}
	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	146 ms	31724 KB	Output is correct
2	Correct	147 ms	31680 KB	Output is correct
3	Correct	147 ms	31620 KB	Output is correct
4	Correct	144 ms	31692 KB	Output is correct
5	Correct	146 ms	31680 KB	Output is correct
6	Correct	149 ms	31612 KB	Output is correct
7	Correct	144 ms	31700 KB	Output is correct
8	Correct	143 ms	31680 KB	Output is correct
9	Correct	148 ms	31700 KB	Output is correct
10	Correct	148 ms	31776 KB	Output is correct
11	Correct	143 ms	31684 KB	Output is correct
12	Correct	146 ms	31688 KB	Output is correct
13	Correct	144 ms	31764 KB	Output is correct
14	Correct	149 ms	31808 KB	Output is correct
15	Correct	148 ms	31688 KB	Output is correct
16	Correct	147 ms	31688 KB	Output is correct
17	Correct	153 ms	31684 KB	Output is correct
18	Correct	143 ms	31640 KB	Output is correct
19	Correct	155 ms	31688 KB	Output is correct
20	Correct	150 ms	31692 KB	Output is correct

Subtask #2

0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	31828 KB	Output is correct
2	Correct	149 ms	31688 KB	Output is correct
3	Correct	149 ms	31720 KB	Output is correct
4	Correct	218 ms	31724 KB	Output is correct
5	Execution timed out	1088 ms	31684 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-