| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19897 |
2016-02-25T06:50:07 Z |
xdoju |
팔찌 (kriii4_V) |
C++14 |
|
579 ms |
21512 KB |
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int MOD = 1000000007ll;
int modpow(int r, int n) {
int ret = 1;
while (n > 0) {
if (n % 2 > 0) {
ret = ((long long)ret * r) % MOD;
}
r = ((long long)r * r) % MOD;
n /= 2;
}
return ret;
}
inline int modinv(int n) {
return modpow(n, MOD - 2);
}
inline int modprod(int a, int b) {
a = a % MOD;
b = b % MOD;
return ((long long)a * b) % MOD;
}
inline int modprod(int a, int b, int c) {
c = c % MOD;
return (modprod(a, b) * (long long)c) % MOD;
}
inline int moddiv(int a, int b) {
return ((long long)a * modinv(b)) % MOD;
}
const int N = 1000000;
int lp[N + 1];
int phi[N + 1];
vector<int> 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];
}
}
}
int geoseries(int k, int cnt) {
if (k == 1) {
return cnt;
}
if (cnt <= 0) {
return 0;
}
int ret = (modpow(k, cnt) - 1 + MOD) % MOD;
ret = modprod(ret, k);
return moddiv(ret, k - 1);
}
int mpow[N + 1];
long long psum[N + 1];
void proc() {
sieve();
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) {
mpow[i] = modpow(k, i);
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
int p = i;
int q = j / i;
psum[j] += modprod(mpow[q], phi[p]);
}
}
long long ssum = 0;
for (int i = 1; i <= n; ++i) {
long long t = 0;
//int lmt = (int)(sqrt(i) + 0.00001);
//for (int p = 1; p <= lmt; ++p) {
/* for (int p = 1; p * p <= i; ++p) {
if (i % p != 0) {
continue;
}
int q = i / p;
t += modprod(mpow[q], phi[p]);
if (p != q) {
t += modprod(mpow[p], phi[q]);
}
}*/
t = moddiv(psum[i] % MOD, i);
ssum += t;
}
int ans = moddiv(ssum % MOD, 2);
int x = moddiv(modprod(k + 1, geoseries(k, n / 2)), 4);
int y = moddiv(geoseries(k, (n + 1) / 2), 2);
ans = (ans + 1) % MOD;
ans = (ans + x) % MOD;
ans = (ans + y) % MOD;
printf("%d", ans);
}
int main() {
//freopen("input.txt", "r", stdin);
proc();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
21512 KB |
Output is correct |
| 2 |
Correct |
13 ms |
21512 KB |
Output is correct |
| 3 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 4 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 5 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 6 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 7 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 8 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 9 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 10 |
Correct |
12 ms |
21512 KB |
Output is correct |
| 11 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 12 |
Correct |
11 ms |
21512 KB |
Output is correct |
| 13 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 14 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 15 |
Correct |
15 ms |
21512 KB |
Output is correct |
| 16 |
Correct |
15 ms |
21512 KB |
Output is correct |
| 17 |
Correct |
17 ms |
21512 KB |
Output is correct |
| 18 |
Correct |
15 ms |
21512 KB |
Output is correct |
| 19 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 20 |
Correct |
8 ms |
21512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
21512 KB |
Output is correct |
| 2 |
Correct |
16 ms |
21512 KB |
Output is correct |
| 3 |
Correct |
13 ms |
21512 KB |
Output is correct |
| 4 |
Correct |
43 ms |
21512 KB |
Output is correct |
| 5 |
Correct |
347 ms |
21512 KB |
Output is correct |
| 6 |
Correct |
420 ms |
21512 KB |
Output is correct |
| 7 |
Correct |
329 ms |
21512 KB |
Output is correct |
| 8 |
Correct |
404 ms |
21512 KB |
Output is correct |
| 9 |
Correct |
463 ms |
21512 KB |
Output is correct |
| 10 |
Correct |
544 ms |
21512 KB |
Output is correct |
| 11 |
Correct |
469 ms |
21512 KB |
Output is correct |
| 12 |
Correct |
522 ms |
21512 KB |
Output is correct |
| 13 |
Correct |
312 ms |
21512 KB |
Output is correct |
| 14 |
Correct |
507 ms |
21512 KB |
Output is correct |
| 15 |
Correct |
296 ms |
21512 KB |
Output is correct |
| 16 |
Correct |
352 ms |
21512 KB |
Output is correct |
| 17 |
Correct |
567 ms |
21512 KB |
Output is correct |
| 18 |
Correct |
328 ms |
21512 KB |
Output is correct |
| 19 |
Correct |
401 ms |
21512 KB |
Output is correct |
| 20 |
Correct |
579 ms |
21512 KB |
Output is correct |
