# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
19834 |
2016-02-25T06:07:05 Z |
xdoju |
팔찌 (kriii4_V) |
C++14 |
|
1000 ms |
18400 KB |
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const long long MOD = 1000000007ll;
long long modpow(long long r, long long n) {
long long ret = 1;
while (n > 0) {
if (n % 2 > 0) {
ret = (ret * r) % MOD;
}
r = (r * r) % MOD;
n /= 2;
}
return ret;
}
long long modinv(long long n) {
return modpow(n, MOD - 2);
}
long long modprod(long long a, long long b) {
a = a % MOD;
b = b % MOD;
return (a * b) % MOD;
}
long long modprod(long long a, long long b, long long c) {
c = c % MOD;
return (modprod(a, b) * c) % MOD;
}
long long moddiv(long long a, long long b) {
return (a * modinv(b)) % MOD;
}
long long gcd(long long a, long long b) {
if (a < b) {
return gcd(b, a);
}
return (b == 0) ? a : gcd(b, a % b);
}
const int N = 1000000;
long long lp[N + 1];
long long phi[N + 1];
vector<long long> 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];
}
}
}
void proc() {
sieve();
long long n, k;
scanf("%lld %lld", &n, &k);
long long ans = 1;
for (long long i = 1; i <= n; ++i) {
long long t = 0;
long long lmt = (long long)(sqrt(i) + 0.00001);
for (long long p = 1; p <= lmt; ++p) {
if (i % p != 0) {
continue;
}
t = (t + modprod(modpow(k, i / p), phi[p])) % MOD;
if (p * p < i) {
t = (t + modprod(modpow(k, p), phi[i / p])) % MOD;
}
}
t = moddiv(t, i);
long long u = 0;
if (i % 2 == 0) {
u = moddiv(t, 2);
long long v = modprod(k + 1, modpow(k, i / 2));
v = moddiv(v, 4);
u = (u + v) % MOD;
}
else {
u = moddiv(t, 2);
long long v = modpow(k, (i + 1) / 2);
v = moddiv(v, 2);
u = (u + v) % MOD;
}
ans = (ans + u) % MOD;
}
printf("%lld", ans);
}
int main() {
//freopen("input.txt", "r", stdin);
proc();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
18400 KB |
Output is correct |
2 |
Correct |
32 ms |
18400 KB |
Output is correct |
3 |
Correct |
30 ms |
18400 KB |
Output is correct |
4 |
Correct |
27 ms |
18400 KB |
Output is correct |
5 |
Correct |
33 ms |
18400 KB |
Output is correct |
6 |
Correct |
29 ms |
18400 KB |
Output is correct |
7 |
Correct |
32 ms |
18400 KB |
Output is correct |
8 |
Correct |
30 ms |
18400 KB |
Output is correct |
9 |
Correct |
32 ms |
18400 KB |
Output is correct |
10 |
Correct |
29 ms |
18400 KB |
Output is correct |
11 |
Correct |
31 ms |
18400 KB |
Output is correct |
12 |
Correct |
24 ms |
18400 KB |
Output is correct |
13 |
Correct |
33 ms |
18400 KB |
Output is correct |
14 |
Correct |
28 ms |
18400 KB |
Output is correct |
15 |
Correct |
32 ms |
18400 KB |
Output is correct |
16 |
Correct |
29 ms |
18400 KB |
Output is correct |
17 |
Correct |
32 ms |
18400 KB |
Output is correct |
18 |
Correct |
28 ms |
18400 KB |
Output is correct |
19 |
Correct |
24 ms |
18400 KB |
Output is correct |
20 |
Correct |
29 ms |
18400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
18400 KB |
Output is correct |
2 |
Correct |
33 ms |
18400 KB |
Output is correct |
3 |
Correct |
34 ms |
18400 KB |
Output is correct |
4 |
Correct |
244 ms |
18400 KB |
Output is correct |
5 |
Execution timed out |
1000 ms |
18400 KB |
Program timed out |
6 |
Halted |
0 ms |
0 KB |
- |