답안 #19010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19010 2016-02-17T02:58:23 Z kriii 팔찌 (kriii4_V) C++14
100 / 100
121 ms 32332 KB
#include <stdio.h>

const long long mod = 1000000007;
const long long inv2 = 500000004;

long long inv[1000001],kpow[1000001],phi[1000001],syn[1000001];

int main()
{
	int N,K;
	scanf ("%d %d",&N,&K);
	
	inv[1] = 1;
	for (int i=2;i<=N;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;

	kpow[0] = 1;
	for (int i=1;i<=N;i++) kpow[i] = kpow[i-1] * K % mod;

	for (int i=1;i<=N;i++){
		phi[i] += i;
		for (int j=i*2;j<=N;j+=i) phi[j] -= phi[i];
	}

	for (int i=1;i<=N;i++){
		syn[i] = (syn[i-1] + kpow[i] * inv[i]) % mod;
	}

	long long ans = 2;
	for (int i=1;i<=N;i++){
		ans = (ans + phi[i] * syn[N/i] % mod * inv[i] % mod) % mod;
	}
	for (int i=1;i<=N;i++){
		if (i & 1) ans = (ans + kpow[i/2+1]) % mod;
		else ans = (ans + (kpow[i/2+1] + kpow[i/2]) * inv2) % mod;
	}
	ans = ans * inv2 % mod;

	printf ("%lld\n",ans);

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 32332 KB Output is correct
2 Correct 0 ms 32332 KB Output is correct
3 Correct 0 ms 32332 KB Output is correct
4 Correct 0 ms 32332 KB Output is correct
5 Correct 0 ms 32332 KB Output is correct
6 Correct 0 ms 32332 KB Output is correct
7 Correct 0 ms 32332 KB Output is correct
8 Correct 0 ms 32332 KB Output is correct
9 Correct 0 ms 32332 KB Output is correct
10 Correct 0 ms 32332 KB Output is correct
11 Correct 0 ms 32332 KB Output is correct
12 Correct 0 ms 32332 KB Output is correct
13 Correct 0 ms 32332 KB Output is correct
14 Correct 0 ms 32332 KB Output is correct
15 Correct 0 ms 32332 KB Output is correct
16 Correct 0 ms 32332 KB Output is correct
17 Correct 0 ms 32332 KB Output is correct
18 Correct 0 ms 32332 KB Output is correct
19 Correct 0 ms 32332 KB Output is correct
20 Correct 0 ms 32332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 32332 KB Output is correct
2 Correct 0 ms 32332 KB Output is correct
3 Correct 0 ms 32332 KB Output is correct
4 Correct 0 ms 32332 KB Output is correct
5 Correct 68 ms 32332 KB Output is correct
6 Correct 91 ms 32332 KB Output is correct
7 Correct 64 ms 32332 KB Output is correct
8 Correct 90 ms 32332 KB Output is correct
9 Correct 94 ms 32332 KB Output is correct
10 Correct 108 ms 32332 KB Output is correct
11 Correct 98 ms 32332 KB Output is correct
12 Correct 105 ms 32332 KB Output is correct
13 Correct 64 ms 32332 KB Output is correct
14 Correct 106 ms 32332 KB Output is correct
15 Correct 64 ms 32332 KB Output is correct
16 Correct 72 ms 32332 KB Output is correct
17 Correct 121 ms 32332 KB Output is correct
18 Correct 73 ms 32332 KB Output is correct
19 Correct 84 ms 32332 KB Output is correct
20 Correct 120 ms 32332 KB Output is correct