Submission #19010

#	Time	Username	Problem	Language	Result	Execution time	Memory
19010		kriii	팔찌 (kriii4_V)	C++14	100 / 100	121 ms	32332 KiB

V

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94